脚本宝典收集整理的这篇文章主要介绍了

[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群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过