寻找有向图中的所有根
我需要找到一个算法来找到有向图中的所有根，在O（n m）。
我有一个寻找单个根的算法：
- 在v中的某些v上运行DFS（v）。如果结果是一个生成树，则v是根。否则，结果就是树木成林。然后：
- 在最后一棵树的根上运行DFS（u）。如果结果是一棵生成树，那么u是根。否则，图中没有根
现在，如果我想找到所有的根，最好的方法是每次在最后一棵树的不同顶点上运行上述算法O（n）次吗？假设我找到了一个根，如果另一个根存在，那么它必须在最后一棵树上，那么如果我继续运行上述算法，直到收到“不存在根”或直到遍历所有顶点，它是O（n m）吗？
提前谢谢！
共有2个答案
首先，您应该在图中找到所有强连通的组件。为了在更短的时间内构建它，可以使用Kosaraju算法或Tarjan算法。所有根都应该位于一个这样的组件中。接下来，您将找到没有传入边的强连接组件。如果有多个这样的组件，则图中没有根顶点。在只有一个组件的情况下，应该检查是否可以从中访问其他组件，在这种情况下，该组件包含图形中的所有根。
老变种。
你应该计算进入顶点的边的数量，这可以用O（m）来完成。所有传入边数为零的顶点都将是图的根，为此需要O（n）时间。
两种方法：
>
反转图形并计算DFS-loop（），注意没有外边的顶点（如阿披舍克所说）。
更高效-在图上运行DFS-循环（），并使用true和false表跟踪没有传入边的顶点。
在最坏的情况下，方法1需要两倍的时间。
-
我需要为一组有向无环图找到从节点 0 开始的最长路径。我正在使用维基百科中的最长路径问题算法。我已经让算法适用于大多数图形，但对于其他图形，它没有给出正确的结果。算法为： 图形实现使用邻接列表来存储图形。如果我传递一个图，例如： 我得到的答案5，这是正确的。但是，如果我通过图表： 然后我得到2，而正确答案应该是3。 我使用的TopSort2算法是： DFS 算法包括：
-
我有一个无向图，我想从一个起始节点列出所有可能的路径。2个节点之间的每个连接在列出的路径中是唯一的，例如，给出以下图表示： 我无法使用现有的算法来完成它，我知道像DFS。任何帮助都将非常感谢。
-
我们可以用这里所述的算法求有向图中的圈数。我需要理解算法。 （1）最后那句话到底有什么用处？对algo的工作原理进行简短的描述会很有帮助。由于算法基本上是统计从一个节点返回到同一节点的周期数，所以我们可以使用另一个数组，称之为v，并做以下技巧： （2）我不能实现我刚才写的算法。这是主要的问题，但我认为我需要理解上面的（1）来理解打印所有循环的代码。 我了解到互联网上有算法，我正在尝试使用这个算法。
-
我试着用谷歌搜索，但是没有任何有价值的东西弹出。 图表： 它是无方向的 表示为具有双边的有向图 可能包含具有负权重的边 我知道我可以使用Bellman Ford在有向情况下解决这个问题，但是对于无向边，它只返回单边（2个循环）作为其输出。我需要找到一个循环的大小 此外，该算法应该具有运行时复杂性O（V*E）和内存复杂性O（V）。
-
设想一个有向无环图如下所示，其中： “a”是根（总是正好有一个根） 每个节点都知道其父节点 节点名称是任意的-不能从中推断出任何内容 我们从另一个来源了解到，节点是按照A到G的顺序添加到树中的（例如，它们是在版本控制系统中提交的） 我可以使用什么算法来确定两个任意节点的最低共同祖先(LCA)，例如： null 注： 从根到给定节点不一定只有一条路径（例如“g”有两条路径），所以不能简单地遍历从根到