Skip to main content

What does pi mean in this BFS algorithm pseudocode? [Resolved]

I have the following pseudocode for breadth-first search algorithm

 1 for each vertex u ? V(G) \ {s}
 2     color[u] = white
 3     d[u] = 8
 4     p[u] = nil
 5 color[s] = gray
 6 d[s] = 0
 7 p[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             p[v] = u
17             Enqueue(Q,v)
18     color[u] = black

Original image

I do not understand what the letter p indicates in this context. I am not familiar with this algorithm and it is a difficult to guess.

I think d indicates the distance, color is of course the color, but that p... it appears to be a variable of some sort but I do not understand its function in this pseudocode.

Question Credit: nbro
Question Reference
Asked December 5, 2018
Posted Under: Programming
2 Answers

I believe the use of p here is actual “parent of”. So in this case, the “parent” of v  is u because we're looking at all nodes adjacent to u.

credit: Heniam
Answered December 5, 2018

The p vector surely keeps the node u with which you came in node v. This helps when you have to build the BFS tree of the graph. Although it is not necessary, this technique reduces a lot the complexity when you have to perform more time the BFS (ex. the Edmonds–Karp algorithm for computing the maximum flow between two nodes in a graph). In this case you don't have to run the BFS more times as you already have the BFS tree constructed and traverse it from the leaves to the root.

credit: Columb
Answered December 5, 2018
Your Answer