[LintCode] Problem 176 - Route Between Two Nodes in Graph

Posted on | In ,

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

Example

Given graph:

1
2
3
4
5
6
	A----->B----->C
\     |
 \    |
  \   |
   \  v
    ->D----->E

No.1

Input:s = B and t = E,

Output:true

No.2

Input:s = D and t = C,

Output:false

Code

1
2
3
4
5
6
7
8
public class DirectedGraphNode {
    int label;
    ArrayList<DirectedGraphNode> neighbors;
    DirectedGraphNode(int x) {
        label = x;
        neighbors = new ArrayList<DirectedGraphNode>();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) {
    Set<DirectedGraphNode> set = new HashSet<>();
    Queue<DirectedGraphNode> queue = new LinkedList<>();

    queue.offer(s);
    set.add(s);

    while (!queue.isEmpty()) {
        DirectedGraphNode node = queue.poll();

        for (DirectedGraphNode neighbor : node.neighbors) {
            if (set.contains(neighbor))
                continue;

            set.add(neighbor);
            queue.offer(neighbor);
        }
    }

    return set.contains(t);
}