Breadth First Search

[Rachelle Jensen]

Hello,

My professor gave us Cormen's Breadth First Search code for Graphs and I've translated all but two for loops into C++ that I simply don't understand.

I can post my own code if necessary. If anyone can just explain the two lines I don't understand in Cormen's though I would really appreciate it! Thank you!

Here is Cormens code:

BFS(G, s)			    // G is the graph and s is the starting node
 1  for each vertex u ∈ V [G] - {s}  // DON'T UNDERSTAND!
 2       do color[u] ← WHITE	    // color of vertex u
 3          d[u] ← ∞		    // distance from source s to vertex u
 4          π[u] ← NIL		    // predecessor of u
 5  color[s] ← GRAY
 6  d[s] ← 0
 7  π[s] ← NIL
 8  Q ← Ø			// Q is a FIFO - queue	
 9  ENQUEUE(Q, s)
10  while Q ≠ Ø		        // iterates as long as there are gray vertices. 
11      do u ← DEQUEUE(Q)
12         for each v ∈ Adj[u]   //DON'T UNDERSTAND
13             do if color[v] = WHITE	
14                   then color[v] ← GRAY	
15                        d[v] ← d[u] + 1
16                        π[v] ← u
17                        ENQUEUE(Q, v)
18         color[u] ← BLACK

[Gaminic]

Line 1: The ∈ signifies "element of". V [G] is the set of all elements (verteces) in graph G.

Adj isn't defined anywhere, but the name and context lead me to believe it's an Adjacency list/matrix.

Both statements just iterate over all elements of a certain set, using u or v as iterator/index.