资讯专栏INFORMATION COLUMN

Graph: Detect cycle

eechen / 1920人阅读

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

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 评论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 评论0 收藏0
  • 261. Graph Valid Tree

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

    Jinkey 评论0 收藏0
  • 算法(第4版) Chapter 4 练习题 答案

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

    13651657101 评论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 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<