World's most popular travel blog for travel bloggers.

Why does a graph traversal algorithm is initialised with visited[s]←true

, ,
Problem Detail:

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} 

visited[s]←_true_; 

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

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};