Route Between Nodes: Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
Hints:#127
解法1
采用广度优先的算法来做，广度优先的话可以找到最短路径：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
public class Graph {
private Node[] nodes;
}
public class Node {
private Node[] children;
}
public boolean hasRoute(Node start, Node dest) {
Queue<Node> nodes = new Queue<>();
start.marked = true;
nodes.enqueue(start);
while (!nodes.isEmpty()) {
Node node = nodes.dequeue();
if (node == dest) {
return true;
}
for (Node child : node.children) {
if (!child.marked) {
if (child == dest) {
return true;
}
chid.marked = true;
nodes.enqueue(child);
}
}
}
return false;
}
|
解法2
虽然可以用深度优先的方法来做，但是这个得碰运气：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public boolean hasRoute(Node start, Node dest) {
if (start.visited) {
return false;
}
start.visited = true;
if (start == dest) {
return true;
}
for (Node n : start.children) {
if (hasRoute(n, dest)) {
return true;
}
}
return false;
}
|
评论