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

Question

到目前为止我找到this纸。它过时了吗？有更快更好的实现吗？

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

Answer 1

如果你使用你所提到的纸张术语和定义有向图的树植根于顶点为r的生成树，具有从r的唯一路径到任何其他顶点，则：

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

所以这个任务将取决于最坏情况下顶点计数的指数时间。考虑到输出的大小（所有生成树），我得出结论，对于任意图，算法不能更快更好地显着。我认为你需要以某种方式重新构建你原来的问题，不要处理所有的生成树，并且可能只是按照某些标准进行搜索。

Answer 2

只无向图....

N 1，N-2跨越发辫是可能的唯一完整的图形....找到任何图形U可以应用此方法的生成树总数.. ...

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