在有向图中找到所有根

本文介绍了在有向图中找到所有根的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我需要找到一种算法来找到有向图中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:

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

在最后一棵树的根上运行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 ?

预先感谢！

推荐答案

两种方法：

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

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.