如何检查有向图是否为无环图？

Question

我如何检查有向图是否为无环图？该算法名称是什么？如果有参考资料将不胜感激。

- Niko

---

另一个支持在SO上“修复”错误答案的情况。 - Sparr

所以，嗯，我主要关心找到它所需的时间。因此，我只需要抽象算法。 - nes1983

你必须遍历所有边并检查所有顶点，因此下限是 O（|V| + |E|）。DFS 和 BFS 的复杂度相同，但如果有递归，则 DFS 更容易编码，因为它可以为您管理堆栈... - ShuggyCoUk

DFS永远不是O(n!)。它只访问每个节点一次，每条边最多访问两次。因此，时间复杂度为O（|V|+|E|）或O(n)。 - Jay Conrod

我的DFS注释是我愚蠢地以无向图的方式思考。 - ShuggyCoUk

Answer 1

我会尝试进行按拓扑排序对图进行排序，如果无法排序，则说明它有环。

- FryGuy

---

这怎么一个票都没有？它在节点和边上是线性的，远远优于O(n^2)的解决方案！ - Loren Pechtel

在许多情况下，DFS（详见J.Conrod的答案）可能更容易，特别是如果无论如何都需要执行DFS。但当然这取决于上下文。 - sleske

拓扑排序将会进入一个无限循环，但它并不会告诉我们循环出现的位置... - Baradwaj Aryasomayajula

也许现在看来有点老了，但是你在 DFS 中标记顶点的访问情况可以告诉你图中是否包含环。如果在自顶向下遍历时访问了该顶点，则将其标记为“打开”，而在自底向上遍历时将其标记为“关闭”。如果你访问了一个“打开”的顶点，则表示图中包含环，否则不包含。 - Jaskirat Singh

Answer 2

仅进行简单的深度优先搜索（DFS）无法很好地找到环。在DFS中，可能会多次访问一个节点而不存在环。而且，根据开始的位置，您也可能不会访问整个图。

您可以按如下方式检查图的连接组件中是否存在环：找到仅具有出边的节点。如果没有这样的节点，则存在环。从该节点开始进行DFS。在遍历每条边时，检查边是否指向已经在您的堆栈上的节点。这表明存在环。如果找不到这样的边，则该连接组件中没有环。

正如Rutger Prins所指出的那样，如果您的图不是连通的，则需要在每个连接组件上重复搜索。

作为参考，Tarjan强连通分量算法与此密切相关。它还将帮助您找到环，而不仅仅是报告它们是否存在。

- Jay

---

顺便提一下：“指向已在堆栈上的节点”的边通常被称为“反向边”，这在文献中是显而易见的。是的，这可能比对图进行拓扑排序更简单，特别是如果您需要执行深度优先搜索。 - sleske

为了让图变成非循环的，需要确保每个连通分量都包含一个仅有出边的节点。您能否推荐一个算法来查找有向图的连通分量（而不是“强”连通分量），以供您的主算法使用？ - kostmo

@kostmo，如果图中有多个连通分量，则在第一次深度优先搜索中将无法访问所有节点。请记录已访问的节点，并使用未访问的节点重复执行算法，直到访问完所有节点。这基本上就是连通分量算法的工作原理。 - Jay Conrod

虽然这个答案的意图是正确的，但如果使用基于堆栈的DFS实现，则答案会令人困惑：用于实现DFS的堆栈将不包含要测试的正确元素。有必要添加一个额外的堆栈到算法中，以跟踪祖先节点集合。 - Theodore Murdock

我有关于你的回答的多个问题。我在这里发布了它们：http://stackoverflow.com/questions/37582599/confusins-on-finding-a-cycle-in-a-directed-graph - Ari

Answer 3

引理22.11在书籍算法导论（第二版）中说明：

如果有向图G是无环的，则对G进行深度优先搜索不会产生后向边。

- Filipe Miguel Fonseca

---

这基本上只是Jay Conrod答案的缩写版 :-). - sleske

同一本书中的一个问题似乎表明存在一种|V|时间算法。答案在这里：https://dev59.com/yXRB5IYBdhLWcg3wv5o_ - Justin

Answer 4

解决方案1：使用Kahn算法检测循环。主要思想：维护一个队列，在队列中加入入度为0的节点。然后逐个取出节点，直到队列为空。检查是否存在任何节点的入边。

解决方案2：使用Tarjan算法检查强连通分量。

解决方案3：使用深度优先搜索(DFS)。使用整数数组标记节点的当前状态： 即0——表示此节点以前未被访问。 -1——表示此节点已被访问，正在访问其子节点。 1——表示此节点已被访问，并已完成。 因此，在进行DFS时，如果节点的状态为-1，则意味着必定存在一个循环。

- Chris Su

Answer 5

我在 Google 的面试中遇到了这个问题。

拓扑排序

你可以尝试使用拓扑排序，其时间复杂度为 O(V + E)，其中 V 是顶点的数量，E 是边的数量。一个有向无环图当且仅当可以进行拓扑排序时才是无环的。

递归删除叶子节点

递归删除叶子节点，直到没有节点剩余，如果剩余超过一个节点，则存在一个环路。除非我理解错了，否则时间复杂度为 O(V^2 + VE)。

类 DFS 算法 ~ O(n + m)

然而，一种高效的类 DFS 算法，最坏情况下的时间复杂度为 O(V + E)：

function isAcyclic (root) {
    const previous = new Set();

    function DFS (node) {
        previous.add(node);

        let isAcyclic = true;
        for (let child of children) {
            if (previous.has(node) || DFS(child)) {
                isAcyclic = false;
                break;
            }
        }

        previous.delete(node);

        return isAcyclic;
    }

    return DFS(root);
}

- tbjgolden

Answer 6

ShuggyCoUk提供的解决方案不完整，因为它可能没有检查所有节点。

def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

这个程序的时间复杂度为O(n+m)或O(n^2)

- Rutger Prins

---

我的确是错误的 - 不过我已经删除了，所以你的现在似乎有点失去了上下文。 - ShuggyCoUk

O(n+m) <= O(n+n) = O(2n)，O(2n) != O(n^2)（翻译：） O(n+m)不超过O(n+n)，也等于O(2n)，但是O(2n)不等于O(n^2)。 - Artur A

使用邻接矩阵表示图时，@Artru 的时间复杂度为O(n^2)，而使用邻接表时为O(n + m)。 - 0x450

嗯... 因为完全图有恰好 m=n^2 条边，所以 m = O(n^2)。因此，O(n+m) = O(n + n^2) = O(n^2)。 - Alex Reinking

Answer 7

这是一个用Swift编写的代码，用于查找图中是否有循环：

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{

    if(breadCrumb[root] == true)
    {
        return true;
    }

    if(visited[root] == true)
    {
        return false;
    }

    visited[root] = true;

    breadCrumb[root] = true;

    if(G[root] != nil)
    {
        for child : Int in G[root]!
        {
            if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
            {
                return true;
            }
        }
    }

    breadCrumb[root] = false;
    return false;
}


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];

var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

这个想法是这样的：使用一个普通的深度优先搜索算法，配合一个用于跟踪已访问节点的数组和另一个用于标记导致当前节点的节点的数组。每当我们执行一个节点的dfs时，我们将其在标记数组中对应的项设置为true，以便在遇到已经访问过的节点时，我们检查其在标记数组中对应的项是否为true。如果为true，则它是导致自身的节点之一（因此形成了一个循环）。技巧在于，每当一个节点的dfs返回时，我们将其对应的标记重新设置为false，这样如果我们从另一条路径再次访问它，就不会被欺骗了。

- m.eldehairy

Answer 8

我知道这是一个老话题，但为了日后查找者的方便，这里提供了我创建的一个C#实现（不保证它是最有效的！）。这个实现旨在使用一个简单的整数来标识每个节点。只要您的节点对象正确地进行哈希和相等处理，您可以随意装饰它。

对于非常深的图形，这可能会有很高的开销，因为它在深度上的每个节点上创建一个哈希集（它们在广度上被销毁）。

您可以输入要搜索的节点以及到该节点的路径。

• 对于只有一个根节点的图，您发送该节点和一个空的哈希集
• 对于具有多个根节点的图，您将其包装在对这些节点的foreach中，并为每次迭代传递一个新的空哈希集

• 在检查给定节点下面的循环时，只需将该节点与空哈希集一起传递即可

  private bool FindCycle(int node, HashSet<int> path)
  {
  
      if (path.Contains(node))
          return true;
  
      var extendedPath = new HashSet<int>(path) {node};
  
      foreach (var child in GetChildren(node))
      {
          if (FindCycle(child, extendedPath))
              return true;
      }
  
      return false;
  }
  

- Matthew

Answer 9

进行深度优先搜索时，不应该存在任何回溯边。在进行深度优先搜索时，跟踪已经访问的节点，如果你遇到当前节点和已有节点之间的边，则表示图中存在环。请保留HTML标签。

- santhosh

Answer 10

Here my implementation in pseudocode:

bool Acyclacity_Test
   InitColor() //Sets to WHITE every vertex
   while there is a node v in V:
      if (v.color == WHITE) then
         tmp = Aux_Acy(v);
         if ( not tmp ) return false
   return true
END

bool Aux_Acy(u)
   u.color = GREY
   for each node v in Adj(u)
       if(v.color == GREY) return false
       else if(v.color == WHITE) tmp = Aux_Acy(v)
       if(!tmp) return false;
   u.color = BLACK
   return true
END

- AlessandroF