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 {
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);
}
|
近期评论