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