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

Graph: Detect cycle

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

Graph: Detect Cycle

Detect if any cycle exists in the graph.

无向图

0 - 1
| /
2

对于无向图,需要记录一个previous node来判断这是不是无向图两个node之间的连接。

DFS

// 0:unvisited, 1:visited, 2:visiting
public boolean hasCycle(Node root, Node prev) {
    if(root.state == 2) {
        return true;
    }
    root.state = 2;
    if(adj.get(root) != null) {
        for(Node node : adj.get(root)) {
            if(node != prev) {
                if(node.status != 1 && hasCycle(node, root)) {
                    return true;
                }
            }
        }
    }
    root.state = 1;
    return false;
}

BFS
同一层的节点会出现相连的情况。

public boolean hasCycle(Node root) {
    Queue<Integer> q = new LinkedList<>();
    if(root != null) q.offer(root);
    root.state = 2;
    while(!q.isEmpty()) {
        Node cur = q.poll();
        for(Node adj : adjacent.get(cur)) {
            // 如果同一层的这个节点是等待访问的,说明这两个节点之间
            // 有连接,所以有环的出现。
            if(adj.state == 2) reture true;
            if(adj.state == 0) {
                q.offer(adj);
                adj.state = 2;
            }
        }
        cur.state = 1;
    }
    return false;
}

有向图

不需要记录previous node;

public boolean hasCycle(Node node) {
    if(node.state == 2) return false;
    node.state = 2;
    if(map.get(node) != null) {
        for(Node adj : map.get(node)) {
            if(adj.state != 1 && hasCycle(adj)) {
                return true;
            }
        }
    }
    node.state = 1;
    return false;
}

总结

以上是脚本宝典为你收集整理的

Graph: Detect cycle

全部内容,希望文章能够帮你解决

Graph: Detect cycle

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

80%的人都看过