8

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.

  • 1
    *Is often the letter π used in pseudocode?* Sometimes, but the meaning will vary depending on the context. – Rufflewind Jun 17 '15 at 03:23
  • 1
    @Snowman: π here is not a function. It is a mutable array of vertices indexed by vertices. – Rufflewind Jun 17 '15 at 03:26
  • 2
    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 08:13
  • @ChristopherWallace: algorithms are at least as much math as they are software development. – RemcoGerlich Jun 17 '15 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 Jun 19 '15 at 05:06

2 Answers2

17

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).

J Trana
  • 1,369
  • 9
  • 17
0

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.

Columb
  • 1