DFS step-wise go through the adjacency list

Question

DFS on a graph G = (V, E) in adjacency list representation:

Search(graph G = (V, E), vertex s ∈ V, integer k)
1   mark vertex s as number k
2   set k ← k + 1
3   let L be the linked list of neighbors for s
4   repeat until all entries in L are marked with an X
5         mark the first un-marked entry y in L with an X (going from left to right in the list)
6         let v be the vertex named in entry y
7         if v is not yet marked with a number then set k ← Search(G, v, k)
8   return k

Here's the initial adjacency list, Search(G, a, 1)

I'm trying to do a step-wise processing to go though this adjacency list. Question is,

4   repeat until all entries in L are marked with an X
5         mark the first un-marked entry y in L with an X (going from left to right in the list)
6         let v be the vertex named in entry y
7         if v is not yet marked with a number then set k ← Search(G, v, k)

• Does one loop from 4 to 7 until L is entirely marked. This may mean that one does not return k (and so do not set s and k) until you reach the end, right? That is you keep resetting k <-- SEARCH(G, v, k).

• Does one keep looping through 4 and 7 until L is marked, and go back to the first marked on L (ie. for G, b, 2) after going to f, one goes back to k <--- SEARCH (G, c, 3)

Can anyone provide next couple steps for reference?

Answer 1

This algorithm for DFS is a little confusing; it could be more simply written. In any case, to answer your question, the loop 4-7 runs till L is entirely marked. (I am not sure what the second question is.)

Indeed, k is being updated by each recursive call to Search(). One point that maybe helps is the following: If you start the search (as in the example) from a, then the algorithm will visit (i.e., mark with numbers) only the nodes that - it can reach starting from a - and have not been visited (i.e., marked with number) already. If you call Search(G, v, k) from some node v and the algorithms visits k' nodes starting from v, then it will return the value k+k'. If the first call is done with k=1, as in the example, then when the algorithm is done, the returned value of k will be equal to the number of nodes it managed to visit in total.

A few steps starting with Search(G,a,k=1):

• Mark a with k = 1. Then, set k=2. Let L(a) be the adjacency list of a. b is the first node in the list of a. Mark b with an x. Since b does not have a number, we run Search(G, b, k=2).
• The recursion first marks b with the number 2 and sets k = 3. Let L(b) be the adjacency list of b. The first entry is a. Mark a with an x just to remember that you have "checked" a from b. But a already has a number, so you skip it anyways. Next entry in L(b) is c. Mark c with an x. Since c does not have a number, you run Search(G, c, k=3).
• The new recursive call marks c with number 3 and sets k=4. Let L(c) be the adjacency list of c. First we check b in the L(c). Mark b with x. But b already has a number, so skip. Then check d. Mark with x and call Search(G, d, 4) and so on..

When the algorithm visits all nodes it can visit starting from d, it will "update k" by the by the total number of nodes visited so far. The execution has now returned to the point where we were considering the list of node c, L(c). There, the only node left unmarked is g. We mark g and (if g has not already been visited in the meantime, we start a search from g). And so on...

Answer 2

Here's what i come up with after doing the whole recursion,