graph - 查找有向加权图的所有生成树

Question

到目前为止，我已经找到了这篇论文。它过时了吗？有没有更快更好的实现？

顺便说一句，维基百科说在无向图中可以有 n^n-2 棵生成树。有向图中可以有多少棵生成树？

Answer 1

仅适用于无向图....

n^n-2 生成树仅适用于完整图......要找到任何图的生成树的总数，您可以应用此方法.....

1. 求图的邻接矩阵。
2. 如果列值由“i”表示，行条目由“j”表示，则...
3. 如果 i=j...那么该值将是顶点的度数
4. 假设，在顶点 v1 和 v2 之间有一条边，那么矩阵条目的值将是 -1......7 如果有两条边，那么它将是 -2......& 等等......
5. 构造邻接矩阵后......排除任何行和列......即第N行和第N列......
6. 答案将是生成树的总数。

Answer 2

如果您使用您提到的论文中的术语并将有向图的生成树定义为以顶点 r 为根的树，具有从 r 到任何其他顶点的唯一路径，则：

很明显，当有向图的生成树数量最多时，最坏的情况是完全图（任何对都有 a->b 和 b->a 边）。如果我们“忘记”方向，我们将得到 n^{n-2} 生成树，就像无向图一样。对于这些生成树中的任何一个，我们都有 n 个选项来选择一个根，并且这个选项定义了我们需要使用的边的唯一定义方向。不难看出，我们得到的所有树都是跨越的，独一无二的，没有其他选择。所以我们得到 n^{n-1} 个生成树。严格证明需要时间，我希望简单的解释就足够了。

因此，在最坏的情况下，这项任务将花费指数时间取决于顶点数。考虑到输出的大小（所有生成树），我得出结论，对于任意图，算法不能明显更快更好。我认为您需要以某种方式重新制定原始问题以不处理所有生成树，并且可能仅需要某些条件进行搜索。