Route Between Nodes
Given a directed graph, design an algorithm to find out whether there is a route between two nodes
Solution
通常的图算法
Code
enum State {Unvisited, Visited, Visiting;}
boolean search(Graph g, Node start, Node end){
if (start == end)
return true;
Stack<Node> curStep = new Stack<Node>();
for (Node u : g.getNodes()){
u.state = State.Unvisited;
}
start.state = State.Visiting;
curStep.push(start);
while (!curStep.isEmpty()){
Node u = curStep.pop();
if (u != null){
for (Node v : u.getAdjacent()){
if (v.state == State.Univisted){
if (v == end){
return true;
}
else{
v.state = State.Visiting;
q.push(v);
}
}
}
}
u.state = State.Visited;
}
return false;
}