查找有向加权图的所有生成树
我发现本文到目前为止。它已经过时了吗？有没有更快更好的实施方案？
顺便说一句，维基百科说无向图中可以有 n^n-2 个生成树。有向图中可以有多少棵生成树？
I have found this paper so far. Is it outdated? Are there any faster and better implementations?
By the way, Wikipedia says that there can be n^n-2 spanning trees in a undirected graph. How many spanning trees can be in a directed graph?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您使用您提到的论文中的术语，并将有向图的生成树定义为以顶点 r 为根的树，具有从 r 到任何其他顶点的唯一路径，则：
很明显，当有向图具有最大数量的生成树时，最坏的情况是完全图（任何对都有 a->b 和 b->a 边）。
如果我们“忘记”方向，我们将得到 n^{n-2} 生成树，就像无向图的情况一样。对于任何这种生成树，我们都有 n 个选项来选择根，并且这个选择定义了我们需要使用的边的唯一定义方向。不难看出，我们得到的所有树都是跨越的、独特的，没有其他选择。这样我们就得到了n^{n-1}个生成树。严格的证明需要时间，我希望简单的解释就足够了。
因此，在最坏的情况下，此任务将花费指数时间，具体取决于顶点数。考虑到输出的大小（所有生成树），我得出的结论是，对于任意图，算法不可能明显更快更好。我认为您需要以某种方式重新表述您的原始问题，以不处理所有生成树，并且可能仅需要按某些标准进行搜索。
If you use terms from paper you mentioned and you define spanning tree of directed graph as tree rooted in vertex r, having unique path from r to any other vertex then:
It's obvious that worst case when directed graph has the greatest number of the spanning trees is complete graph (there are a->b and b->a edges for any pair).
If we "forget" about directions we will get n^{n-2} spanning trees as in case of undirected graphs. For any of this spanning trees we have n options to choose a root, and this choice define uniquely define directions of edges we need to use. Not hard to see, that all trees we get are spanning, unique and there are no nother options. So we get n^{n-1} spanning trees. Strict proof will take time, I hope that simple explanation is enough.
So this task will take exponential time depend from vertex count in worst case. Considering the size of output (all spanning trees), I conclude that for arbitrary graph, algorithm can not be significantly faster and better. I think you need to somehow reformulate your original problem to not deal with all spanning trees, and may be search only needed by some criteria.
仅适用于无向图....
n^n-2 生成树仅适用于完整图....要查找任何图的生成树的总数，您可以应用此方法.....
for undirected graph only....
n^n-2 spanning tress are possible for only complete graph....to find total number of spanning trees of any graph u can apply this method.....