Friday, March 8, 2013

[Cracking the Code Interview 4th edition] 4.2

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Thought: BFS.

Initialize all the points' state as unvisited.
Start.state = visiting
q.in(start)
while(q is not empty) {
       tmp = q.out(start) ;
       for ( v adjacent to tmp) {
             if (v.state is unvisited) {
                   if (v = end) { return true; }
                   else {
                         v.state = visiting;
                         q.in(v);
                   }
             }
       }
       tmp.state = visited;
}
return false;

No comments:

Post a Comment