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
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.
-
1Is often the letter π used in pseudocode? Sometimes, but the meaning will vary depending on the context.Rufflewind– Rufflewind2015年06月17日 03:23:41 +00:00Commented Jun 17, 2015 at 3:23
-
1@Snowman: π here is not a function. It is a mutable array of vertices indexed by vertices.Rufflewind– Rufflewind2015年06月17日 03:26:20 +00:00Commented Jun 17, 2015 at 3:26
-
2In 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– Brandin2015年06月17日 08:13:57 +00:00Commented Jun 17, 2015 at 8:13
-
@ChristopherWallace: algorithms are at least as much math as they are software development.RemcoGerlich– RemcoGerlich2015年06月17日 12:14:18 +00:00Commented Jun 17, 2015 at 12:14
-
Now that this question has been reopened, can someone with sufficient moderator privileges please nuke the comments here? If I were landing on this page for the first time, they would add less than zero to my quest for knowledge...J Trana– J Trana2015年06月19日 05:06:58 +00:00Commented Jun 19, 2015 at 5:06
2 Answers 2
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. This verbiage can be found here (PDF link).
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.