Ali Buch in Python: Sec. 2-5 Graph

Seite 93: Zweiteilige Diagrammbeurteilung

from Graph import join_dic  #Den Inhalt finden Sie im Vorbereitungsartikel
from Graph import d_to_ud  #Den Inhalt finden Sie im Vorbereitungsartikel

#############Machen Sie ein gerichtetes Diagramm###########
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)   ###Ich möchte es rekursiv verarbeiten, also mache es zu einem ungerichteten Diagramm

for i in graph:
    if isinstance(graph[i], list):
        continue
    else:
        graph[i] = [graph[i]]   #### for i in graph[hoge]Damit kann die Verarbeitung mit vereinheitlicht werden, 

#Nachtrag) if not isinstance(graph[i],list)Ich hätte es tun sollen.

color = (N) * [0]

def coloring(start, col):  ##Können Sie die Verbindungskomponente malen, zu der der Knotenstart gehört?

    color[start] = col

    for i in graph[start]:
        if color[i] == col:  ##Heraus, wenn benachbarte Standorte dieselbe Farbe haben
            return False
        if color[i] == 0 and (not coloring(i, -col)):　 ##Wenn die angrenzende Stelle farblos ist, malen Sie von dort aus mit der entgegengesetzten Farbe
            return False

    return True


def solve():
    for i in graph:
        if color[i] == 0:
            if not coloring(i, 1):    ##Können Sie von i ausgehen und die Verbindungskomponente anwenden?
                print("No")
                return 0

    print("Yes")
    return 0


solve()

Eingang:

4  
0 1
1 2
2 3
0 3

Ausgabe:

Yes

Eingang:

3
0 1
1 2
2 0

Ausgabe:

No

Da der Graph nicht immer verkettet ist, müssen alle Knoten betrachtet werden.

Seite 95: Bellmanford-Methode

Eingang:

3

0 1 1
1 2 1
0 2 3

0

2

Ausgabe:

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 ist eine klassifizierte Version, die von @sishiracamus in den Kommentaren des Vorbereitungsartikels geschrieben wurde.