脚本宝典收集整理的这篇文章主要介绍了[LintCode] Route Between Two Nodes in Graph [DFS/BFS],脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
Problem
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
Note
若s为有向图的终点,经过下一次dfs,会指向null,返回false;否则,只要s所有neighbors的深度搜索中包含满足条件的结果,就返回true。
Solution
public class Solution {
public boolean hasRoute(ArrayList<DirectedGraphNode> graph,
DirectedGraphNode s, DirectedGraphNode t) {
Set<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>();
return dfs(s, t, visited);
}
public boolean dfs(DirectedGraphNode s, DirectedGraphNode t, Set<DirectedGraphNode> visited) {
if (s == null) return false;
if (s == t) return true;
visited.add(s);
for (DirectedGraphNode next: s.neighbors) {
if (visited.contains(next)) continue;
if (dfs(next, t, visited)) return true;
}
return false;
}
}
BFS
public class Solution {
public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) {
if (s == t) return true;
Deque<DirectedGraphNode> q = new ArrayDeque<>();
q.offer(s);
Set<DirectedGraphNode> visited = new HashSet<>();
while (!q.isEmpty()) {
DirectedGraphNode node = q.poll();
visited.add(node);
if (node == t) return true;
for (DirectedGraphNode child : node.neighbors) {
if (!visited.contains(child)) q.offer(child);
}
}
return false;
}
}
以上是脚本宝典为你收集整理的[LintCode] Route Between Two Nodes in Graph [DFS/BFS]全部内容,希望文章能够帮你解决[LintCode] Route Between Two Nodes in Graph [DFS/BFS]所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。