# What does pi mean in this BFS algorithm pseudocode?

I have the following pseudocode for breadth-first search algorithm

``````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
``````

Original image

I do not understand what the letter π 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 `π`... it appears to be a variable of some sort but I do not understand its function in this pseudocode.

• @Snowman I'd go with the style used in computer science and academic publications rather than math specifically, but I do agree with the general idea. This question is asking about this usage might have been answered by reading the wikipedia page, and π is not something in common use but rather specific to how the author writes the algorithm. I worry that there are far too many variations on pseudocode and asking about what each character in each style means could get out of hand. – user40980 Jun 17 '15 at 1:54
• Is often the letter π used in pseudocode? Sometimes, but the meaning will vary depending on the context. – Rufflewind Jun 17 '15 at 3:23
• @Snowman: π here is not a function. It is a mutable array of vertices indexed by vertices. – Rufflewind Jun 17 '15 at 3:26
• In this context π is just a symbol used in the algorithm, similar to d and color. Sometimes algorithm writers like to use single letter symbols rather than cute names like "parentVertices" or something that might tend to be used in a programming language. – Brandin Jun 17 '15 at 8:13
• @Snowman Are you joking? It is not a math question. It is about interpreting a pseudocode to write a program, why should this not be about software development, I really cannot understand. – nbro Jun 17 '15 at 9:51

## 2 Answers

I believe the use of π 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.

The π 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.