Falsche Ausgabe in Tiefe Erste Suche Implementierung

Question

Kürzlich habe ich einen Code für Tiefensuche zuerst auf einer Website (https://brilliant.org/wiki/depth-first-search-dfs/) gesucht. Doch ihre Umsetzung nicht vollständig correct.This ist der Code, den sie

geschrieben

def depth_first_search(graph): 
    visited, stack = set(), [root] 
    while stack: 
     vertex = stack.pop() 
     if vertex not in visited: 
      visited.add(vertex) 
      stack.extend(graph[vertex] - visited) 
    return visited 

Wie Sie sehen können, angewendet die Logik sie korrekt ist, aber sie verwendet gesetzt Betrieb, der die Ausgabe jedes Mal das Programm läuft ändert.

Das ist mein komplettes Programm

graph = {'A': {'B', 'S'}, 'B': {'A'}, 'C': {'S', 'F', 'D', 'E'}, 
    'D': {'C'}, 'E': {'H', 'C'}, 'F': {'C', 'G'}, 'G': {'S', 'F', 'H'}, 
    'H': {'G', 'E'}, 'S': {'A', 'G', 'C'}} 

def depth_first_search(graph, root): 
    visited, stack = set(), [root] 
    while stack: 
     vertex = stack.pop() 
     if vertex not in visited: 
      visited.add(vertex) 
      stack.extend(graph[vertex] - visited) 
    return visited 

print(depth_first_search(graph, 'A')) 

Im Folgenden sind die Ausgänge ich evertime ich das Programm laufen

{'H', 'C', 'B', 'A', 'D', 'S', 'F', 'E', 'G'} 
{'D', 'E', 'C', 'H', 'G', 'S', 'A', 'B', 'F'} 
{'G', 'F', 'C', 'H', 'E', 'D', 'B', 'S', 'A'} and so on.... 

Der Grund für die besonders Satz verwendet Sinn für die folgenden Codezeile wie wir macht möchte, dass der Stapel nur die nicht erkundeten Scheitelpunkte speichert.

stack.extend(graph[vertex] - visited) 

So Durchführung Einstelldifferenzdruck Betrieb wird erreicht, dass objective.But es zu einem Preis kommt, wie erwähnt above.So ich den Code ein bisschen gezwickt mit Satz zu vermeiden und mit Listen tun machen

graph = {'A': ['B', 'S'], 'B': ['A'], 'C': ['S', 'F', 'D', 'E'], 
'D': ['C'], 'E': ['H', 'C'], 'F': ['C', 'G'], 'G': ['S', 'F', 'H'], 
    'H': ['G', 'E'], 'S': ['A', 'G', 'C']} 

def depth_first_search(graph, root): 
    visited, stack = [], [root] 
    while stack: 
     vertex = stack.pop() 
     if vertex not in visited: 
      visited.append(vertex) 
      neighbours = graph[vertex] 
      for neighbour in neighbours: 
       # ensures we only add unexplored nodes to the stack 
       if neighbour not in visited: 
        stack.append(neighbour) 
    return visited 

print(depth_first_search(graph, 'A')) 

Aber ich bekomme ein falsches Ergebnis

['A', 'S', 'C', 'E', 'H', 'G', 'F', 'D', 'B'] 

Das richtige Ergebnis

sein muss 10

Was mache ich falsch?

Answer 1

Die Antwort, die Sie erhalten, ist eine gültige DFS-Reihenfolge für dieses Diagramm. Es scheint eine ungeschriebene Einschränkung zu geben, dass die Nachbarn eines Knotens in alphabetischer Reihenfolge durchlaufen werden müssen. In diesem Sinne zwei Dinge:

Zuerst fügen Sie die Nachbarn eines Knotens dem Stapel in der Reihenfolge hinzu, in der sie definiert sind. Aber wenn Sie pop() vom Stapel entfernen, nehmen Sie zuerst den letzten Artikel vom Stapel. Das bedeutet, dass Sie Ihre Knoten in umgekehrter Reihenfolge auswählen. Das ist leicht genug, um zu beheben, indem die Reihenfolge umgekehrt, in dem Sie über die Nachbarn iterieren:

for neighbour in reversed(neighbours): 

Zweitens haben Sie nicht wirklich den Nachbars Knoten definiert in alphabetisch. Sie müssen entweder die Werte von in der Definition alphabetize oder sortieren sie vor Iterieren:

for neighbour in reversed(sorted(neighbours)): 
# or 
for neighbour in sorted(neighbours, reverse=True): 

Answer 2

Es sieht aus wie die anfängliche Codebeispiel Sie haben keine topologischen Art produzieren soll, sondern einfach alle aufzulisten Knoten, die von der Wurzel aus erreicht werden können. Wahrscheinlich ist es wichtig zu bemerken, dass es nicht inkorrekt ist, es soll Ihnen einfach keine Bestellung geben.

Ihr Code tut im Grunde, was er sagt, und die Ausgabe, die Sie bekommen, ist so korrekt wie die, die Sie erwarten. Solange du nur ein DFS willst.

denke ich, was er verpasst hat, dass, wenn Sie rufen vertex = stack.pop() Sie vergessen, dass es immer wieder die letzte (dh am weitesten rechts stehende Element), und wenn Sie stack.append(neighbour) nennen, sind Sie die Kinder auf den Stapel schieben in der Reihenfolge von links nach rechts.

Wenn Sie möchten, dass ein DFS zuerst den Zweig "ganz links" zuerst verlässt, müssen Sie die Reihenfolge der Nachbarn/Kinder umkehren, bevor Sie sie dem Stapel hinzufügen.

EDIT: Ich habe nicht genug rep frei noch kommentieren, aber meine Antwort ist im Wesentlichen der gleiche wie glibdud ist. Es sieht so aus, als ob das Problem darin besteht, dass Sie zusätzliche Einschränkungen in Ihrem Kopf anwenden, die nicht Teil eines einfachen DFS sind.