检测未连接图中的周期 [英] Detect cycles in unconnected graph

问题描述

尽管对此主题有一些疑问，但在更具体的问题上我仍需要一些建议.

Although there are a few questions on this topic, i would need some piece of advice in a more specific matter.

我正在一些必须重命名实体的项目中工作.这意味着要保存一个包含对象的旧名称和新名称的新对象.这就是软件的工作方式.

I am working on some project where i have to rename an entity. This implies saving a new object containing the old and the new name of the entity. This is how the soft works.

现在，我要做的就是检查在有人尝试重命名对象时是否尝试了循环依赖.例如:

Now, what i have to do is check if a circular dependency is attempted when someone tries to rename an object. For example:

A -> B
B -> C
C -> A

当某人尝试将C重命名为A时，应发出信号.

When someone tries to rename C into A, this should be signaled.

我不确定如何解决此问题.我的想法是创建一个有边[A，B]，[B，C]，[C，A]的有向图，并应用一些循环检测算法来查找圆形依赖关系(Tarjan或类似的东西).

I am not sure how to approach this problem. My thought was to create a directed graph having the edges[A, B], [B, C], [C, A] and the apply some cycle detecting algorithms to find the circular dependencies (Tarjan or something).

考虑到图形将不被连接是否有效?可能有上述示例，然后:

Would that be efficient considering that the graph will not be connected? It is possible to have the aforementioned example and then:

E -> F
H -> J
X -> Y

我最终会遇到很多未连接的边缘，也许会有几个周期.我应该首先找到较小的，连通的图并在每个图上应用任何算法，还是有可能只添加构建大图并在其上应用算法?

I will end up with a lot of unconnected edges and a few cycles maybe. Should i first find the smaller, connected graphs and apply whatever algorithm on each or is there a possibility to just add build the big one and apply the algorithm on it?

对于我的示例，检测循环依赖关系的最快和推荐的方法是什么?

What is the fastest and recommended way to detect the circular dependencies for my example?

谢谢！

更新我想出了以下dfs方法:

Update I have come up with the following dfs approach:

void DFS(int root, boolean[] visited){
        onStack = new boolean[N];
        edgeTo = new int[N];

        visited[root]=true;
        onStack[root] = true;

        for (int i=0; i<N; ++i){
            if (G[root][i]){ 
                if(!visited[i]){
                   DFS(i,visited);
                } else if (onStack[i]){
                   System.out.printf("%nCycle %n");
                }
          } else {
              System.out.printf("%nG[" + root + "][" + i + "] is not an edge%n");
          }

          onStack[root] = false;
        }

    }

并这样称呼它:

void DFS()
    {
        boolean[] visited =new boolean[N]; 
        int numComponets=0;

        // do the DFS from each node not already visited
        for (int i=0; i<N; ++i)
            if (!visited[i] && cycle == null)
            {
                ++numComponets;             
                DFS(i,visited);
            } 
    }

它成功地找到了连接的组件，但是不识别任何周期，只有当我删除G [root] [i]条件时，那将是从0到0的第一个周期.我缺少什么?

And it successfully finds the connected components, but does not recognize any cycle, only if i remove the G[root][i] condition, that would be the first cycle from 0 to 0. What am i missing?

推荐答案

您只需维护所有节点的一组 S .然后，从该集合中选取一个节点，在该节点上运行dfs/bfs，检查后边缘(如果是，则知道您有一个循环).对于您访问的每个节点，从集合 S 中删除该节点.dfs/bfs完成后，请检查 S 是否为空.如果是这样，那么您就知道没有周期.否则，您从 S 中获取一个节点，然后在该节点上运行dfs/bfs.运行时应为O(n)，其中n是节点数.

You can simply maintain a set S of all nodes. Then you take a node from that set, run dfs/bfs on that node, checking for back edges (if so, you know you have a cycle). For each node you visit, remove that node from the set S. After dfs/bfs is finished, you check if S is empty. If so, then you know there are no cycles. Otherwise, you take a node from S, and run dfs/bfs on that node. The runtime should be O(n), where n is the number of nodes.

伪代码:

S = set(all nodes)
while len(S) > 0:
    node = S.pop()
    stack = [node]
    visited = set()
    while len(stack) > 0:
        node = stack.pop()
        visited.add(node)
        S.remove(node)
        for each neighbor of node in your graph:
            if neighbor in visited:
                # you know you have a cycle

            else:
                stack.append(node)

这篇关于检测未连接图中的周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！