java - 检测未连接图中的循环

Question

虽然关于这个主题有一些问题，但我需要一些更具体的建议。

我正在开发一个项目，我必须重命名一个实体。这意味着保存一个包含实体的旧名称和新名称的新对象。这就是软件的工作原理。

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

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

当有人尝试将 C 重命名为 A 时，应该发出信号。

我不知道如何解决这个问题。我的想法是创建一个具有边 [A，B]，[B，C]，[C，A] 的有向图，并应用一些循环检测算法来查找循环依赖关系(Tarjan 或其他东西)。

考虑到图不会连接，这会有效吗？可以有前面提到的例子，然后:

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

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

检测我的示例的循环依赖关系的最快且推荐的方法是什么？

谢谢!

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

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 的第一个循环。我错过了什么？

Answer 1

您可以简单地维护所有节点的集合S。然后，您从该集合中取出一个节点，在该节点上运行 dfs/bfs，检查后边缘(如果是这样，您就知道有一个循环)。对于您访问的每个节点，从集合 S 中删除该节点。 dfs/bfs 完成后，检查 S 是否为空。如果是这样，那么您就知道不存在循环。否则，您从 S 获取一个节点，并在该节点上运行 dfs/bfs。运行时间应该是 O(n)，其中 n 是节点数。

伪代码:

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)