9

I have the following pseudocode for breadth-first search algorithm

BFS(G,s)
 1 for each vertex uV(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 vAdj[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.

  • 2
    @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
  • 1
    Is often the letter π used in pseudocode? Sometimes, but the meaning will vary depending on the context. – Rufflewind Jun 17 '15 at 3:23
  • 1
    @Snowman: π here is not a function. It is a mutable array of vertices indexed by vertices. – Rufflewind Jun 17 '15 at 3:26
  • 1
    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
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.

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.