如何检查有向图是无环的?

How do I check if a directed graph is acyclic? And how is the algorithm called? I would appreciate a reference.

如何检查有向图是无环的?这个算法是怎么调用的呢?我很感激你的推荐。

9 个解决方案

#1

I would try to sort the graph topologically, and if you can't, then it has cycles.

我会试着对图进行拓扑排序，如果不行，就会有循环。

#2

Doing a simple depth-first-search is not good enough to find a cycle. It is possible to visit a node multiple times in a DFS without a cycle existing. Depending on where you start, you also might not visit the entire graph.

做一个简单的深度优先搜索还不足以找到一个循环。在没有循环存在的DFS中，可以多次访问一个节点。取决于您从哪里开始，您也可能不会访问整个图形。

You can check for cycles in a connected component of a graph as follows. Find a node which has only outgoing edges. If there is no such node, then there is a cycle. Start a DFS at that node. When traversing each edge, check whether the edge points back to a node already on your stack. This indicates the existence of a cycle. If you find no such edge, there are no cycles in that connected component.

您可以在图的连接组件中检查循环，如下所示。找到一个只有输出边的节点。如果没有这样的节点，那么就有一个循环。在该节点上启动DFS。当遍历每条边时，检查边缘是否指向已经在堆栈上的节点。这表明存在一个循环。如果你没有找到这样的边，在那个连接的组件中没有循环。

As Rutger Prins points out, if your graph is not connected, you need to repeat the search on each connected component.

正如Rutger Prins所指出的，如果您的图没有连接，您需要在每个连接的组件上重复搜索。

As a reference, Tarjan's strongly connected component algorithm is closely related. It will also help you find the cycles, not just report whether they exist.

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

#3

Lemma 22.11 on the Book Introduction to Algorithms (Second Edition) states that:

Lemma 22.11在《算法导论》(第二版)中指出:

A directed graph G is acyclic if and only if a depth-first search of G yields no back edges

一个有向图G是无环的，如果且仅当一个深度优先搜索G没有返回边缘。

#4

Solution1： Kahn algorithm to check cycle. Main idea: Maintain a queue where node with zero in-degree will be added into queue. Then peel off node one by one until queue is empty. Check if any node's in-edges are existed.

Solution1:卡恩算法检查周期。主要思想:在队列中保持一个节点为零的节点。然后逐个剥离节点，直到队列为空。检查是否存在任何节点的边缘。

Solution2: Tarjan algorithm to check Strong connected component.

解决方案2:Tarjan算法检查强连接组件。

Solution3: DFS. Use integer array to tag current status of node: i.e. 0 --means this node hasn't been visited before. -1 -- means this node has been visited, and its children nodes are being visited. 1 -- means this node has been visited, and it's done. So if a node's status is -1 while doing DFS, it means there must be a cycle existed.

环境:DFS。使用integer数组来标记节点的当前状态:即0——意味着这个节点之前没有访问过。-1——表示已访问该节点，并访问其子节点。1——表示这个节点已经访问过了，已经完成了。因此，如果一个节点的状态是-1，而DFS，则意味着存在一个周期。

#5

The solution given by ShuggyCoUk is incomplete because it might not check all nodes.

ShuggyCoUk给出的解决方案是不完整的，因为它可能不检查所有节点。


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

This has timecomplexity O(n+m) or O(n^2)

这timecomplexity O(n + m)或O(n ^ 2)

#6

I know this is an old topic but for future searchers here is a C# implementation I created (no claim that it's most efficient!). This is designed to use a simple integer to identify each node. You can decorate that however you like provided your node object hashes and equals properly.

我知道这是一个古老的话题，但对于未来的搜索者来说，这是我创建的c#实现(没有说它是最有效的!)这是为了使用一个简单的整数来标识每个节点。您可以根据您的节点对象散列和适当的值来进行修饰。

For Very deep graphs this may have high overhead, as it creates a hashset at each node in depth (they are destroyed over breadth).

对于非常深的图，这可能会有很高的开销，因为它在每个节点上创建了一个hashset(它们在宽度上被破坏)。

You input the node from which you want to search and the path take to that node.

您输入要搜索的节点，并将路径带到该节点。

For a graph with a single root node you send that node and an empty hashset
对于一个具有单个根节点的图，您将发送该节点和一个空的hashset。
For a graph having multiple root nodes you wrap this in a foreach over those nodes and pass a new empty hashset for each iteration
对于具有多个根节点的图形，您可以将其封装在这些节点之上，并为每个迭代传递一个新的空hashset。

When checking for cycles below any given node, just pass that node along with an empty hashset

当检查任何给定节点下面的循环时，只需将该节点与一个空的hashset一起传递。

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;
}

#7

There should not be any back edge while doing DFS.Keep track of already visited nodes while doing DFS,if you encounter a edge between current node and existing node,then graph has cycle.

在做DFS时，不应该有任何后边。在做DFS时跟踪已经访问过的节点，如果您在当前节点和现有节点之间遇到一条边，则图具有循环。

#8

here is a swift code to find if a graph has cycles :

这是一个快速的代码，以发现图表是否有循环:

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)

The idea is like this : a normal dfs algorithm with an array to keep track of visited nodes , and an additional array which serves as a marker for the nodes that led to the current node,so that when ever we execute a dfs for a node we set its corresponding item in the marker array as true ,so that when ever an already visited node encountered we check if its corresponding item in the marker array is true , if its true then its one of the nodes that let to itself (hence a cycle) , and the trick is whenever a dfs of a node returns we set its corresponding marker back to false , so that if we visited it again from another route we don't get fooled .

想法是这样的:正常dfs算法跟踪数组的访问节点,和一个额外的数组作为标记的节点导致当前节点,所以,当我们为一个节点执行dfs组标记数组中相应的项目是真实的,所以,当一个已经访问节点遇到我们检查标记数组中相应的项目是正确的,如果它真的那么它的一个节点,让本身(因此一个周期),诀窍是，每当节点返回的dfs返回时，我们将相应的标记设置为false，这样，如果我们从另一条路径再次访问它，我们就不会被愚弄。

#9

Here is my ruby implementation of the peel off leaf node algorithm.

这是我的ruby实现的剥叶节点算法。

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end

#1