Graph: Detect cycle

eechen 发布于2019-08-14 15:01 / 1914人阅读

摘要：无向图对于无向图，需要记录一个来判断这是不是无向图两个之间的连接。同一层的节点会出现相连的情况。如果同一层的这个节点是等待访问的，说明这两个节点之间有连接，所以有环的出现。有向图不需要记录

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 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;
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65233.html

[基本算法] Detect Cycle in Directed/Undirected Graph 有

摘要：不在的话，表示不构成环，我们应该合并这两个集合因为加上这条边，两个集合就被连起来了，合并成了一个集合注意如果想要复杂度为必须用路径压缩。并查集写法参考注意方法用找的老大哥，合并的是的老大哥。 Detect Cycle in Directed Graph 有向图找环 Given n nodes labeled from 0 to n - 1 and a list of directed...

ymyang 2019-08-14 14:04 评论0 收藏0
Graph: Topological Sort

Graph: Topological Sort 利用和detect cycle类似的思路，用dfs + recursion解决。并且一定时一个有向图。 Stack stack = new Stack(); // 0:unvisit, 1:visited, 2:visiting public boolean topologicalSort(Node node) { if(node.stat...

ShevaKuilin 2019-08-14 15:01 评论0 收藏0
261. Graph Valid Tree

摘要：题目链接检查图的连通性及是否有环，可以，，从一个点出发看能不能遍历所有的点，同时来检查是否有环。还可以用检查是否有环，最后看的数量是否等于来判断是不是。 261. Graph Valid Tree 题目链接：https://leetcode.com/problems... 检查图的连通性及是否有环，可以dfs，bfs，从一个点出发看能不能遍历所有的点，同时visited来检查是否有环。...

Jinkey 2019-08-16 10:29 评论0 收藏0
算法（第4版） Chapter 4 练习题答案

摘要：离心率计算题目释义计算点的离心率，图的直径，半径，中心计算图的围长定义点的离心率图中任意一点，的离心率是图中其他点到的所有最短路径中最大值。图的中心图中离心率长度等于半径的点。改动离心率计算，在遍历中增加的赋值即可。离心率计算 4.1.16 The eccentricity of a vertex v is the the length of the shortest path fr...

13651657101 2019-08-14 17:13 评论0 收藏0
【Change Detection系列一】$digest 在Angular新版本中重生

摘要：感谢您的阅读如果喜欢这篇文章请点赞。它对我意义重大，它能帮助其他人看到这篇文章。对于更高级的文章，你可以在或上跟随我。 I’ve worked with Angular.js for a few years and despite the widespread criticism I think this is a fantastic framework. I’ve started w...

legendaryedu 2019-08-21 17:59 评论0 收藏0