Algorithms – What Does Pi Mean in This BFS Algorithm Pseudocode?

algorithmsnotationpseudocode

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.

Best Answer

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

Related Solutions

Pseudocode – Definition and Uses

Pseudocode is, as the name implies, not real code, but it looks like code. It helps people to understand a problem domain or solution better without having to add all the baggage necessary when using a real language.

In short: it's used only for illustrational purposes.

Pseudocode and programming
There is no definition or fixed rule of pseudocode, it can be different each time. It is not a (real) programming language and no-one will consider it one. It cannot be compiled or used as a real programming language: if you could do that, it ceases to be pseudocode. Pseudocode does not need to be deterministic (a necessity for computers to compile), it rather needs to be understood by humans. To use pseudocode, you'll have to convert it to your favorite programming language. This conversion process can be different each time and no rules can be given for it because, again, pseudocode is like free speech: it can take any form.

Usages
It is commonly used, especially in the design phase of projects to help understand a certain approach to a problem. It's also commonly used in algorithm design, or when teachers draw something on the board. In all these cases it is not necessary to compile the code, you just want to understand the problem/solution.

Types of pseudocode
Pseudocode can be, but doesn't have to be of a certain type, i.e., you can have a stack-based pseudocode to illustrate MSIL, you can have an imperative pseudocode to illustrate Java, C#, C++, Python, you can have a functional pseudocode to illustrate F#, Haskell, SQL etc.

Examples
From the top of my head, but anything goes, because pseudocode can be invented on the spot:

XML pseudocode, showing a head+body structure that allows for multiple p-elements:

<head ...
   <title ...
</
<body ...>
   (<p>...)+
</

Imperative pseudocode, showing the diamond problem in languages that support multiple inheritance:

class A() { readFile(); }
class B() : A {}       // overrides readFile in A
class C() : A {}       // overrides readFile in A
class D() : B, C {}    // what definition of readFile should be used?

The above two examples obviously resemble some (type of) language, but aren't really that language and cannot possibly compile. They rather illustrate something that you want to explain.

Algorithms – Possible Improvements to Damerau-Levenshtein Algorithm

I had to look up the Damerau-Levenshtein distance on wikipedia, so forgive me if this is wrong. But it looks like it only allows for transposing adjacent letters and not any arbitrary ones. So your example "abcdef" -> "abcfad" with transpose of d and f doesn't work. It seems to me you have modified the definition of the algorithm and are no longer calculating the Damerau-Levenshtein distance.

Best Answer

Related Solutions

Pseudocode – Definition and Uses

Algorithms – Possible Improvements to Damerau-Levenshtein Algorithm

Related Topic