Is this algorithm actually a graph-traversal algorithm?

Question

I was given in a lecture the following algorithm that wwas said to be a graph-traversal algorithm.

The algorithm given during the lecture

The algorithm

EXPLORE (s:sommet, D:list of the following vertices of the vertices ahead,
var visited:tab)
var: LIST:list; i,j: vertexes;
visited[s]←_true_;
LIST←{s}
While LISTE ≠ 0
    Select i∈LIST
    if ∃ j ∈ D[i], not visited[j]
    visited[j]←true;
    Else LIST←LIST-{i}

PARCOURS(D: list of the out-going vertices or ahead vertices)
for all vertex x in X
     {visited [x]<-false}
for all x in X
    if not visited [x]
    EXPLORE(x,D,M or visited)

the example I tried

\begin{array}{|l|cr|} x & \Gamma^+(x)\\ \hline X1 & X2,X4 \\ X2 & X1,X3\\ X3 & X4,X5 \\ X4 & X6,X7 \\ X5 & X2,X6 \\ X6 & X4,X7 \\ X7 & \emptyset \\ \end{array}

I assume that this is the list (tell me if you think this is not the case).

Select 1 $\in$ LIST

LIST(1)=X2,X4 $\not= \emptyset$

X2 $\in$ LISTE(1) is not visited, so we change visited2 to true X4 $\in$ LISTE(1) is not visited, so we change visited[4] to true no more elements are not visited, we do LISTE <-LISTE-(1)

the array-list thus becomes:

\begin{array}{|l|cr|} x & \Gamma^+(x)\\ \hline X2 & \not X1,X3\\ X3 & X4,X5 \\ X4 & X6,X7 \\ X5 & X2,X6 \\ X6 & X4,X7 \\ X7 & \emptyset \\ \end{array}

And I can plot $X1$

Then I do the algorithm again

Select 1 $\in$ LIST

LIST(2)=X3 $\not= \emptyset$

X3 $\in$ LISTE(2) is not visited, so we change visited$[3]$ to true no more elements are not visited, we do LISTE <-LISTE-(2)

the array-list thus becomes:

\begin{array}{|l|cr|} x & \Gamma^+(x)\\ \hline X3 & X4,X5 \\ X4 & X6,X7 \\ X5 & \not X2,X6 \\ X6 & X4,X7 \\ X7 & \emptyset \\ \end{array}

I can plot anew:

Then I'm not sure wether to SELECT X4 or X3. It seems that it is the whole difference between Depth-first search algorithm and Breadth-first search ones.

I think this the way the first part of this algorithm run, yet I'm not sure on how does the second partt works. It seems that it allows to explores every paths in my mere opinion...

The algorithm given by a friend of mine

Yet, a friend of mine just wrote the following one rather shorter to do the same thing:

EXPLORE (s:sommet, D:list of the following vertices of the vertices ahead,
var visited:tab)
var: LIST:list; i,j: vertexes;
visited[s]←_true_;
LIST←{s}
While LISTE ≠ 0
    Select i∈LIST
    if ∃ j ∈ D[i], not visited[j]
    visited[j]←true;
    LIST←LIST+{j};
    Else LIST←LIST-{i}

I don't understand how the first one is a graph traversal algorithm and I wonder if it is the best one as far as it seems that the second one is shorter, (but unclearly to me actually).

Answer 1

There seems to be a bug in the first algorithm which is fixed in the second algorithm, namely the first EXPLORE explores only the starting vertex and its neighbors, but nothing beyond that. However, the first algorithm at least explores the entire graph; the second one only explores the connected component of $s$. The second one also doesn't bother to initialize the array visited.

I strongly suggest that you try and understand what these algorithms are doing. It could help running them manually on a few examples. You could also program them and have the programs print out the actions performed by the algorithms.