# Is this algorithm actually a graph-traversal algorithm?

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

• This is just a list traversal algorithm written in an ugly lopsided pseudo-Pascal, with typos and with a lot of useless notation added to it. (For example, X pops out of nowhere in PARCOURS, vertices can't be out-going (they don't go anywhere, arcs may be though). I believe that the artists' original intention was breadth-first traversal, but you would be much better off using some actual programming language which has appropriate graph data-structure to try and implement one (or find an implementation for). Sep 27 '15 at 13:31
• Ok, on wikipedia for instance? I've seen that there is some articles on depth-first search algos and Breadth-first search ones. Actually I was just trying to understand what my lecturer gave... :( ;) Sep 27 '15 at 13:43
• Well, if you are given a graph in a form of adjacency list, and all you want from traversal is that you visit each vertex once, then you just visit all the elements in the list, which just makes it a list traversal. Also, if, as per your example, you can have all your vertices in a list even before traversal: why bother inventing anything? - you can again, just visit every vertex in that list. Breadth / depth first traversal only makes sense when you only can get hold of one of the vertices and you'd start exploring from that one. Sep 27 '15 at 14:13

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.
• What revealed you that the first EXPLORE only explores the starting vertex and its neigbourghs and is the issue fixed by PARCOURS? And how did you found that second one only explores the connected component of $s$? They seems to do the same thing but the second EXPLORE add a "just visited vertex" to a list, but I'm not sure how does it works. I have an example, I think I'm going to add it to the question, because its the first time I run algorithms. Thank you for the advice! Sep 27 '15 at 12:52