benötigen einen Graphen-Algorithmus ähnlich wie DFS

Question

Ich bin gespannt, ob es einen bestimmten Graph-Algorithmus ist, der eine ungewichtete azyklischen gerichteten Graphen durchläuft durch einen Startknoten auswählen und dann über DFS fortfahren. Wenn ein Knoten gefunden wird, die nicht recherchierten Vorgänger hat, dann sollte es wieder um die eingehenden Pfade verfolgen, bis alle Pfade beginnen erkundet worden sind.

fand ich eine wikipedia Kategorie für Graphenalgorithmen aber es ist ein kleines Meer von Algorithmen hier und ich bin mit den meisten von ihnen nicht vertraut sind.

EDIT: Beispiel: den Graphen angegeben {AB, EB, BC, BD}, Traverse als: {A, B, E, B, C, D} oder eindeutige Reihenfolge wie {A, B, E, C, D}. Notieren Sie sich diesen Algorithmus im Gegensatz zu BFS oder DFS muss nicht wieder beginnen an einem neuen Startknoten, wenn alle Pfade des ersten Startknoten erschöpft sind.

Answer 1

In der DFS, Sie in der Regel wählen die Ecke besucht werden, nachdem u an den Rand basierend auf u beginnen. Sie wollen zuerst an u an den Rändern, wählen endet. Um dies zu tun, könnten Sie haben eine transponieren Graph Info, und versuchen, den Scheitelpunkt bekommen von dort zuerst.

Es wäre so etwas wie dies:

procedure dfs(vertex u)
  mark u as visited
  for each edge (v, u) //found in transpose graph
    if v not visited
      dfs(v)
  for each edge (u, w)
    if v not visited
      dfs(w)

Answer 2

Was Sie suchen ist die topologische Sortierung. Soweit mir bekannt gibt es keine einfache Möglichkeit, eine Grafik in seiner topologisch sortierten Reihenfolge ohne precomputation.

zu durchqueren

Der Standard Weg, um den TOPSORT zu bekommen, ist ein Standard-DFS zu tun, und dann speichern Sie die besuchten Knoten in der Reihenfolge ihrer Besuchszeiten. Schließlich Umkehrung dieser Knoten und voila, Sie haben sie in der gewünschten Reihenfolge.

Pseudocode:

list topsort

procedure dfs(vertex u)
  mark u as visited
  for each edge (u, v)
    if v not visited
      dfs(v)
  add u to the back of topsort

Die Liste topsort enthält dann die Eckpunkte in der umgekehrten Reihenfolge, die Sie wollen. umkehren nur die Elemente des TOPSORT, dass zu korrigieren.

Answer 3

Wenn Sie sich für topological sort suchen, können Sie dies auch, da eine Adjazenzliste (oder eine Liste von Kanten (u,v), die Sie in O(E) Zeit vorverarbeiten können):

list top_sort( graph in adjacency list )
     parent = new list
     queue = new queue
     for each u in nodes
         parent(u) = number of parents
         if ( parent(u) is 0 ) // nothing points to node i
             queue.enqueue( u )

     while ( queue is not empty )
         u = queue.pop
         add u to visited
         for each edge ( u, v )
             decrement parent(v) // children all have one less parent
             if ( parent(v) is 0 )
                 queue.enqueue( v )

eine adjacency list (oder eine Liste von Kanten (u,v)) Gegeben ist diese O( V + E ), da jede Kante zweimal berührt wird - einmal Zuwachs, einmal zu dekrementieren, in O(1) Zeit jedem. Bei einer normalen Warteschlange, jeder vertice wird auch von der Warteschlange höchstens zweimal verarbeitet werden. - die auch mit einer Standard-Warteschlange in O(1) getan werden kann,

Beachten Sie, dass dies unterscheidet sich von der DFS (zumindest eine straight-up-Implementierung), dass sie behandelt Wälder.

Ein weiteres interessantes Detail ist, dass, wenn Sie queue mit einem priority_queue ersetzen irgendeine Art von Struktur / Anordnung zur Einführung, können Sie tatsächlich geben die Ergebnisse in einer bestimmten Reihenfolge sortiert.

Zum Beispiel für eine kanonische Klasse Abhängigkeitsgraphen (Sie können nur Klasse X nehmen, wenn Sie Klasse Y haben):

100:
101: 100
200: 100 101
201: 
202: 201

würden Sie wahrscheinlich bekommen, als Ergebnis:

100, 201, 101, 202, 200

aber wenn man es so ändern, dass Sie immer nehmen wollen niedrigere Nummern Klassen zuerst, man kann leicht zurück ändern:

100, 101, 200, 201, 202