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

Question

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

Answer 1

我想尝试拓扑排序的图形，如果你做不到，那它有周期。

Answer 2

做一个简单的深度优先搜索的不的不够好，找一个周期。它可以多次访问节点在DFS不存在的周期。根据你的地方开始，你可能还不能访问整个图形。

可以在一个图形的一个连接的组件检查循环如下。发现它只有出边的节点。如果没有这样的节点，然后有一个周期。在该节点启动DFS。当遍历每个边，检查边缘是否回指向一个节点已经在栈上。这表明一个周期的存在。如果你发现没有这样的优势，也有在连接组件中没有循环。

由于鲁特格尔普林斯指出，如果你的图形没有连接，你需要重复每个连接的组件上的搜索。

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

Answer 3

引理22.11对图书Introduction to Algorithms（第二版）规定：

  

一个向图G是无环的，当且仅当一个深度优先搜索的G产生无后边缘

Answer 4

<强>解决方法1 ：<强>卡恩算法来检查循环即可。主要思想：保持其中具有在度零节点将被添加到队列中的队列中。然后通过一个直到队列为空剥离节点之一。检查是否有任何节点的入边都存在。

<强>溶液2 ：<强>的Tarjan算法以检查强连接成分

<强> Solution3 ：<强> DFS 即可。使用整型数组来标记节点的当前状态： 即0 --means此节点之前没有被访问。      -1 - 表示该节点已被访问，并参观了正在其子节点。      1 - 表示该节点已被访问，而它的完成。 所以，如果一个节点的状态为-1，而做DFS，这意味着必须有一个周期的存在。

Answer 5

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

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

这具有timecomplexity O（N + M）或为O（n ^ 2）

Answer 6

我知道这是一个老话题，但对于未来的搜索者，这里是我创建的 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;
  }
  

Answer 7

有不应该任何后边缘，而这样做已经访问过的节点的DFS.Keep轨道，而这样做DFS，如果遇到当前节点和现有节点之间的边缘，然后图具有周期。

Answer 8

这里是一个迅速代码以发现有图有循环：

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对于一个节点，我们的标志器阵列作为真正在设置相应的项目，使以往任何时候都已经访问节点的时候遇到我们，检查标志器阵列中的相应的项目是真实的，如果它真，那么它可以让自身的一个节点 （因此一个周期），而关键是，每当一个节点返回的DFS我们设置了相应的标记回假，所以，如果我们从其他途径再次访问它，我们不会上当。

Answer 9

下面是我的红宝石实施剥离叶的节点算法。

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 10

刚刚有了在谷歌这个问题采访。

拓扑排序

可以尝试排序拓扑，这是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);
}