Given a directed graph, design an algorithm to find out whether there is a route be- tween two nodes.
Page 1 of 1
Given a directed graph, design an algorithm to find out whether there is a route be- tween two nodes.
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;
}
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;
}
Similar topics
» Design an algorithm and write code to serialize and deserialize a binary tree/graph
» You are given a TreeNode, and you have to write an algorithm which will return the no. of nodes in the tree.
» Find the height of BST
» To find the successor of x in a BST
» Find whether two BST are the same. Recursively and Iteratively
» You are given a TreeNode, and you have to write an algorithm which will return the no. of nodes in the tree.
» Find the height of BST
» To find the successor of x in a BST
» Find whether two BST are the same. Recursively and Iteratively
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
|
|