在有向图中找到所有根 [英] Finding all the roots in a directed graph

问题描述

我需要找到一种算法来找到有向图中O（n + m）中的所有根。

I need to find an algorithm for finding all the roots in a directed graph, in O(n+m).

我有一种算法可以找到单个root：

I have an algorithm for finding a single root:

1. 在V中的某些v上运行DFS（v）。如果结果是单个生成树，则v是根。否则，结果是一片森林。然后：


2. 在最后一棵树的根上运行DFS（u）。如果结果是单个生成树，则u是根。否则，图中没有根。

现在，如果我想找到所有根，则是运行的最佳方法上述算法O（n）次，每次在最后一棵树的不同顶点上？假设我找到一个根，如果另一个根存在，那么它必须在最后一棵树上，如果我继续运行上述算法直到接收到不存在根或遍历所有顶点，它是否为O（n + m）？

Now if I want to find all the roots, is the best way to just run the above algorithm O(n) times, on a different vertex in the last tree every time ? Assuming I found a root, if another root exists then it must be on the last tree, then is it O(n+m) if I continue to run the above algorithm until receiving "no root exists" or until going over all vertices ?

预先感谢！

推荐答案

两种方法：

1. 反转图形并计算DFS-loop（）并注意没有出边的顶点（如Abhishek说的那样）。

1. Reverse the graph and calculate DFS-loop() and note the vertices which have no outgoing edges (like Abhishek said).

更高效-使用真，假表在图形上运行DFS-loop（）并跟踪没有传入边的顶点。

More efficient - Run DFS-loop() on the graph and keep track of vertices with no incoming edges using a true, false table.

在最坏的情况下，方法1花费的时间是原来的两倍。

Method 1 takes twice as long in the worst case.

这篇关于在有向图中找到所有根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！