Co oznacza pi w tym pseudokodzie algorytmu BFS?

Mam następujący pseudokod dla pierwszego algorytmu wyszukiwania

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

Oryginalny obraz

Nie rozumiem, co litera π wskazuje w tym kontekście. Nie znam tego algorytmu i trudno go zgadnąć.

Myślę, że dwskazuje odległość, colorto oczywiście kolor, ale to π... wydaje się być jakąś zmienną, ale nie rozumiem jej funkcji w tym pseudokodzie.

Uważam, że użycie π tutaj jest faktycznym „rodzicem”. Więc w tym przypadku „rodzicem” v   jest u, ponieważ patrzymy na wszystkie węzły sąsiadujące z u .

Wektor π z pewnością utrzymuje węzeł u, z którym przyszedłeś do węzła v. Pomaga to w budowaniu drzewa BFS wykresu. Chociaż nie jest to konieczne, ta technika znacznie zmniejsza złożoność, gdy trzeba wykonać więcej czasu BFS (np. Algorytm Edmondsa – Karpa do obliczania maksymalnego przepływu między dwoma węzłami na wykresie). W takim przypadku nie musisz uruchamiać BFS więcej razy, ponieważ masz już zbudowane drzewo BFS i przechodzisz z liści do katalogu głównego.