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

View previous topic View next topic Go down

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

Post  Admin on Thu Aug 25, 2011 9:14 pm

public enum State{
Unvisited, Visiting, Visited;
}

public boolean find(Node n1, Node n2, Graph g){
Queue<Node> q=new Queue<Node>();
q.enqueue(n1);
for(Node d: g.getNodes()){
d.state=State.Univisited;
}

while(!q.isEmpty()){
Node current=q.remove();
for(Node v: current.getAdjacent()){
if(v.state==State.visited)
return true;
else{
v.state=State.Visiting;
q.enqueue(v);
}
}
current.state=State.visited;
}
return false;
}

Admin
Admin

Posts: 131
Join date: 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

View previous topic View next topic Back to top

- Similar topics

Permissions in this forum:
You cannot reply to topics in this forum