Ich habe folgende Pseudo - Code für die Breitensuche Algorithmus
BFS(G,s)
1 for each vertex u ∈ V(G) \ {s}
2 color[u] = white
3 d[u] = ∞
4 π[u] = nil
5 color[s] = gray
6 d[s] = 0
7 π[s] = nil
8 Q = ∅
9 Enqueue(Q,s)
10 while q ≠ ∅
11 u = Dequeue(Q)
12 for each v ∈ Adj[u]
13 if color[v] == white
14 color[v] = gray
15 d[v] = d[u] + 1
16 π[v] = u
17 Enqueue(Q,v)
18 color[u] = black
Ich verstehe nicht, was der Buchstabe π in diesem Zusammenhang anzeigt. Ich bin mit diesem Algorithmus nicht vertraut und es ist schwer zu erraten.
Ich denke, dzeigt die Entfernung an, colorist natürlich die Farbe, aber das π... es scheint eine Variable zu sein, aber ich verstehe ihre Funktion in diesem Pseudocode nicht.
Antworten:
Ich glaube, dass die Verwendung von π hier tatsächlich "Eltern von" ist. Also in diesem Fall die „Eltern“ von v sind u , weil wir an allen Knoten neben freuen u .
quelle
Der π-Vektor behält sicher den Knoten u bei, mit dem Sie in Knoten v gekommen sind. Dies ist hilfreich, wenn Sie den BFS-Baum des Diagramms erstellen müssen. Obwohl dies nicht erforderlich ist, reduziert diese Technik die Komplexität erheblich, wenn Sie mehr Zeit für das BFS benötigen (z. B. den Edmonds-Karp-Algorithmus zur Berechnung des maximalen Flusses zwischen zwei Knoten in einem Diagramm). In diesem Fall müssen Sie das BFS nicht mehrmals ausführen, da Sie den BFS-Baum bereits erstellt haben, und ihn von den Blättern zur Wurzel durchlaufen.
quelle