如何检查有向图是否是非循环的？

Question

如何检查有向图是否是非循环的？ 以及该算法是如何调用的？ 我希望能提供参考。

Answer 1

我会尝试对图进行拓扑排序，如果不能，那么它就有循环。

Answer 2

进行简单的深度优先搜索不足以不足以找到循环。 在 DFS 中可以多次访问一个节点而不存在循环。 根据您开始的位置，您也可能不会访问整个图表。

您可以按如下方式检查图形的连接组件中的循环。 找到一个只有出边的节点。 如果不存在这样的节点，则存在环路。 在该节点上启动 DFS。 遍历每条边时，检查该边是否指向堆栈中已有的节点。 这表明循环的存在。 如果找不到这样的边，则该连接组件中不存在循环。

正如 Rutger Prins 指出的那样，如果您的图未连接，则需要对每个连接的组件重复搜索。

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

Answer 3

算法简介（第二版）一书中的引理 22.11 指出：

有向图 G 是非循环的当且仅当 G 的深度优先搜索没有产生后边

Answer 4

方案一：Kahn算法检查循环。 主要思想：维护一个队列，将入度为零的节点添加到队列中。 然后将节点一一剥离，直到队列为空。 检查是否存在任何节点的入边。

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

解决方案3：DFS。 使用整数数组来标记节点的当前状态：
即0——表示该节点之前未被访问过。
-1——表示该节点已被访问，并且其子节点正在被访问。
1——表示该节点已被访问，并且已完成。
所以如果一个节点在进行DFS时状态为-1，则说明一定存在环路。

Answer 5

刚刚在谷歌面试中遇到了这个问题。

拓扑排序

你可以尝试拓扑排序，即 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(child) || DFS(child)) {
                isAcyclic = false;
                break;
            }
        }

        previous.delete(node);

        return isAcyclic;
    }

    return DFS(root);
}

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)

Answer 7

我知道这是一个老话题，但对于未来的搜索者，这里是我创建的 C# 实现（没有声称它是最有效的！）。 这样做的目的是使用一个简单的整数来标识每个节点。 只要你的节点对象散列和等于正确，你就可以按照你喜欢的方式装饰它。

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

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

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

• 当检查低于任何值的循环时给定节点，只需将该节点与空哈希集一起传递

  private bool FindCycle(int 节点, HashSet 路径) 
    { 
  
        if (路径.包含(节点)) 
            返回真； 
  
        var ExtendedPath = new HashSet(path) {node}; 
  
        foreach（GetChildren（节点）中的 var child） 
        { 
            if (FindCycle(子级, 扩展路径)) 
                返回真； 
        } 
  
        返回假； 
    } 
    

Answer 8

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

Answer 9

这里有一个快速代码来查找图是否有循环：

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 算法，带有一个用于跟踪访问节点的数组，以及一个附加数组，该数组用作导致当前节点的节点的标记节点，这样当我们对节点执行 dfs 时，我们将标记数组中的相应项设置为 true ，这样当遇到已访问过的节点时，我们检查标记数组中其相应项是否为 true ，如果为 true那么它是让自己的节点之一
（因此是一个循环），诀窍是每当节点的 dfs 返回时，我们将其相应的标记设置回 false ，这样，如果我们从另一条路线再次访问它，我们就不会被愚弄。

Answer 10

这是我的 剥离叶子节点算法的 ruby​​ 实现< /a>.

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

Answer 11

这是我的伪代码实现：

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

Answer 12

您可以使用我的答案中的查找循环反转 https://stackoverflow.com/a/60196714/1763149

def is_acyclic(graph):
    return not has_cycle(graph)