Question
Problem Statement
Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
Example
Given graph:
A----->B----->C
\ |
\ |
\ |
\ v
->D----->E
for s = B
and t = E
, return true
for s = D
and t = C
, return false
题解1 - DFS
检测图中两点是否通路,图搜索的简单问题,DFS 或者 BFS 均可,注意检查是否有环即可。这里使用哈希表记录节点是否被处理较为方便。深搜时以起点出发,递归处理其邻居节点,需要注意的是处理邻居节点的循环时不是直接 return, 而只在找到路径为真时才返回 true, 否则会过早返回 false 而忽略后续可能满足条件的路径。
Java
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
|
public class Solution {
public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) {
Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>(); return dfs(graph, s, t, visited); }
public boolean dfs(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t, Set<DirectedGraphNode> visited) {
if (s == t) { return true; } else { if (s == null || t == null) return false; visited.add(s); if (s.neighbors.size() > 0) { for (DirectedGraphNode node : s.neighbors) { if (visited.contains(node)) continue; if (dfs(graph, node, t, visited)) return true; } } }
return false; } }
|
源码分析
根据构造函数的实现,Java 中判断是否有邻居节点时使用.size
,而不是null
. 注意深搜前检测是否被处理过。行 1
| if (dfs(graph, node, t, visited)) return true;
|
中注意不是直接 return, 只在为 true 时返回。
复杂度分析
遍历所有点及边,时间复杂度为 \[O(V+E)\].
题解2 - BFS
除了深搜处理邻居节点,我们也可以采用 BFS 结合队列处理,优点是不会爆栈,缺点是空间复杂度稍高和实现复杂点。
Java
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
|
public class Solution {
public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) {
if (graph == null || s == null || t == null) return false;
Queue<DirectedGraphNode> q = new LinkedList<DirectedGraphNode>(); Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>(); q.offer(s); while (!q.isEmpty()) { int qLen = q.size(); for (int i = 0; i < qLen; i++) { DirectedGraphNode node = q.poll(); visited.add(node); if (node == t) return true; if (node.neighbors.size() > 0) { for (DirectedGraphNode n : node.neighbors) { if (visited.contains(n)) continue; q.offer(n); } } } }
return false; } }
|
源码分析
同题解一。
复杂度分析
时间复杂度同题解一,也是 \[O(V+E)\], 空间复杂度最坏情况下为两层多叉树,为 \[O(V+E)\].