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}
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).
X
pops out of nowhere inPARCOURS
, 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). $\endgroup$