graph - 测试 G 是否包含树状的算法

Question

有向图 G 的树状图是一棵有根树，使得从根到图中每个其他顶点都有一条有向路径。给出一个有效且正确的算法来测试 G 是否包含树状结构，及其时间复杂度。

我只能想到从每个节点运行 DFS/BFS，直到在一个 DFS 中所有节点都被覆盖。
我想过使用最小生成树算法，但这也仅适用于无向图

有没有其他有效的算法？

我发现了一个后续问题，其中说明有一个 O(n+m) 算法，任何人都可以帮助解决什么问题吗？

Answer 1

您正在寻找的是所谓的埃德蒙算法。最小生成树算法不适用于有向图，但这就是想法。当图形是有向的并且树状就是你上面描述的时候，MST 问题就变成了树状问题。

朴素的复杂度是 O(EV)，就像 Prim 的无向 MST 问题算法一样，但我相信它有更快的实现。

有关更多信息，您可以查看 wiki 页面:

Edmonds Algorithm