检测未连接图中的循环

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

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

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

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

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

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

考虑到图不会连接，这是否有效？可以有上述示例，然后：

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

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

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

谢谢你！

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

你可以简单地维护一个集合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)