2
$\begingroup$

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

graph Exemple For Running Test

\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$ 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:

X1->X2

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – wvxvw Sep 27 '15 at 13:31
  • $\begingroup$ 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... :( ;) $\endgroup$ – ThePassenger Sep 27 '15 at 13:43
  • $\begingroup$ 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. $\endgroup$ – wvxvw Sep 27 '15 at 14:13
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – ThePassenger Sep 27 '15 at 12:52
  • $\begingroup$ I repeat my recommendation of your trying to understand this on your own. Once you get more experienced, you will be able to make such deductions from the code on your own. $\endgroup$ – Yuval Filmus Sep 27 '15 at 12:54
  • $\begingroup$ okay, I'm trying right now with an example! Thank you! $\endgroup$ – ThePassenger Sep 27 '15 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.