World's most popular travel blog for travel bloggers.

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

, , No Comments
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} 

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?

Asked By : Marine1
Answered By : David Richerby

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}; 
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47483

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback