Code For NonGeek
Would you like to react to this message? Create an account in a few clicks or log in to continue.

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

Go down

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

Post  Admin Thu Aug 25, 2011 4: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

https://codefornongeek.forumotion.com

Back to top Go down

Back to top

- Similar topics

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