Livre Ali en python: Graphique Sec.2 à 5

page93: Jugement de graphe en deux parties

from Graph import join_dic  #Voir l'article de préparation pour le contenu
from Graph import d_to_ud  #Voir l'article de préparation pour le contenu

#############Créer un graphe orienté###########
N = int(input())
graph = {}
while 1:
    edge = input()
    if edge == "":
        break

    edge = list(map(int, edge.split()))
    dic = {edge[0]: edge[1]}
    graph = join_dic(graph, dic)
##########################################

graph = d_to_ud(graph)   ###Je veux le traiter de manière récursive, alors faites-en un graphe non dirigé

for i in graph:
    if isinstance(graph[i], list):
        continue
    else:
        graph[i] = [graph[i]]   #### for i in graph[hoge]Pour que le traitement puisse être unifié avec, 

#Postscript) if not isinstance(graph[i],list)J'aurais dû le faire.

color = (N) * [0]

def coloring(start, col):  ##Pouvez-vous peindre le composant de connexion auquel appartient le nœud de départ?

    color[start] = col

    for i in graph[start]:
        if color[i] == col:  ##Out si les sites adjacents sont de la même couleur
            return False
        if color[i] == 0 and (not coloring(i, -col)):　 ##Si le site adjacent est incolore, commencez à peindre à partir de là avec la couleur opposée pour commencer
            return False

    return True


def solve():
    for i in graph:
        if color[i] == 0:
            if not coloring(i, 1):    ##Pouvez-vous commencer à partir de i et appliquer le composant de connexion?
                print("No")
                return 0

    print("Yes")
    return 0


solve()

contribution:

4  
0 1
1 2
2 3
0 3

production:

Yes

contribution:

3
0 1
1 2
2 0

production:

No

Le graphe n'étant pas toujours concaténé, il est nécessaire de regarder tous les nœuds.

page95: Méthode Bellmanford

contribution:

3

0 1 1
1 2 1
0 2 3

0

2

production:

2

import mygraph

print("number of nodes")
N = int(input())

print("input graph")
graph = mygraph.WeightedGraph()

while 1:

    inputline = input()

    if inputline == "":
        break

    inputline = list(map(int, inputline.split()))

    graph.join(inputline[0], inputline[1], inputline[2])

graph = graph.undirected()


for node in graph:
    if not isinstance(graph[node][0], list):
        graph[node] = [graph[node]]

print("Start?")
startpos = int(input())
print("Goal?")
goalpos = int(input())


dp = N * [float("INF")]


while 1:

    update = False

    dp[startpos] = 0

    for from_node in graph:

        neighbors = graph[from_node]

        for [to_node, weight] in neighbors:

            if dp[from_node] != float("INF") and dp[to_node] > dp[from_node] + weight:

                dp[to_node] = dp[from_node] + weight

                update = True

    if not update:
        break

print(dp[goalpos])

mygraph.py est une version classifiée écrite par @sishiracamus dans les commentaires de l'article de préparation.