Erkennen eines Zyklus in einem ungerichteten Graphen mit DFS

Question

Ich habe den folgenden Code, der eine Modifikation von DFS ist, die erkennt, ob ein ungerichteter Graph einen Zyklus hat.

Egal wie mein Diagramm aussieht, es gibt immer wahr und ich kann nicht herausfinden, was ich falsch mache. Der Algorithmus funktioniert, wenn ich ihn auf Papier zeichne, aber die Implementierung führt nicht zu funktionierendem Code.

Answer 1

Ihr Code besucht als Nachbar den Knoten, von dem Sie gerade gekommen sind, und so fahren Sie die gleiche Kante vorwärts und rückwärts, nur um zu sehen, dass Sie bereits den Knoten besucht haben, von dem Sie tatsächlich kamen. Aber der Algorithmus schließt fälschlicherweise, dass dies einen Zyklus darstellt.

Es reicht also nicht zu prüfen, ob bereits ein Nachbar besucht wurde. Dies stellt nur einen Zyklus dar, wenn die entsprechende Kante noch nicht zuvor gefahren wurde.

Eine Möglichkeit, den Algorithmus zum Laufen zu bringen, besteht darin, die Kante auf dem Stapel zu speichern, nicht nur einen Knoten. Dann können Sie einfach überprüfen, ob ein Nachbar das andere Ende der Kante ist, und dann ist es einfach ignorieren:

def find_cycle(graph, start): 
    colors = { node : "WHITE" for node in graph } 
    colors[start] = "GRAY" 
    stack = [(None, start)] # store edge, but at this point we have not visited one 
    while stack: 
     (prev, node) = stack.pop() # get stored edge 
     for neighbor in graph[node]: 
      if neighbor == prev: 
       pass # don't travel back along the same edge we came from 
      elif colors[neighbor] == "GRAY": 
       return True 
      else: # can't be anything else than WHITE... 
       colors[neighbor] = "GRAY" 
       stack.append((node, neighbor)) # push edge on stack 
    return False 

Beachten Sie, dass die Grafik, die Sie in der Frage vorgelegt einen Zyklus hat:

A---C 
/ \ 
B---E---F 

Wenn Sie nehmen die Verbindung zwischen C und F (zum Beispiel) heraus, der obige Code wird False zurückgeben.

Answer 2

Ihr Algorithmus ist für einen ungerichteten Graphen nicht korrekt. Du wirst einen Zyklus als die allererste Kante zwischen A und B erkennen (B ist ein Nachbar von A und A ist ein Nachbar von B).