0
$\begingroup$

I just had a course on algorithm, we just started to study graph traversal. the teacher wrote analgorithm but I think there is a mistake: I'm a bit shy so I didn't asked her why so...

EXPLORE (s:sommet, D:dictionnary of the following vertexes or ahed of vertexes,
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 LISTE←LISTE-{i}

I'm not sure about this line:

visited[s]←_true_;

What does that mean? shouldn't it be false? At the begining, we haven't visited any vertexes yet?

$\endgroup$
1
$\begingroup$

Suppose you don't mark the start vertex as visited. As you explore the graph, you might come back to the start and begin to explore from there again. Since the first thing you do is visit the start, it's marked as visited at the start of the algorithm.

However, the given algorithm clearly doesn't perform a graph traversal. It adds the start node to the list, then marks all its neighbours as visited, one at a time, then deletes the start node from the list, then terminates. The line

visited[j]←true;

should be

visited[j]←true; LIST←LIST+{j};
$\endgroup$

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.