检测非连通图中的环

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

- BadWolf

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)

- jh314

---

在这种情况下，实际上不需要路径搜索算法。 "图"将具有单向路径，直到有人尝试将实体重命名为先前的名称，在这种情况下，您只需检测该名称/节点是否已被使用即可。 - João Neves

不完全是这样。因为如果我尝试将 C 重命名为 X，即使我已经将 X 存储在列表中，这也应该可以工作。 - BadWolf

@user3502249 这样不会创建一个循环吗？ - João Neves

一个循环不一定在使用先前的命名时就闭合，而是当同一实体经历了一些命名之后又回到先前的名称时才算是闭合。这样的情况可以被称为： - BadWolf

A -> B, B -> A A -> B, B -> C, C -> A A -> B, B -> X, X -> Y, Y -> Z, Z -> A - BadWolf

Answer 2

如果我正确理解了您的问题，那么只有当某人将实体的名称更改为先前由该实体使用的名称时，才会出现循环依赖。

考虑到这一点，为什么不只是创建一个包含实体所有名称的集合，并且每当用户尝试更改名称时检查名称是否在您的集合中。如果是，则会创建循环依赖；如果不在您的集合中，则将其添加到集合中并允许名称更改操作继续。

像HashSet这样的集合对于此方法非常有用，因为它为元素查找提供了平均O(1)的时间复杂度。

- João Neves