生成两个节点之间的边数

Question

我使用Kruskal算法生成了此最小生成树，并且很难在两个节点之间生成路径。有人可以帮我伪代码吗？我尝试使用邻接表和邻接矩阵 通用标签

Answer 1

如果您只想要两个节点之间的任何路径，则宽度优先搜索可以，并且会生成最短路径（因为它的生成树最小）。

Answer 2

根据定义，生成树没有循环（或循环），因此最多两个节点之间只能有一条路径（即“路径”，不是复数）。

也许我不明白这个问题。您是否要查找树中两个给定节点的连接方式？

如果是这样，在我看来，这是最简单的暴力手段，在这种情况下，最糟糕的情况是O（Edges）从一个点沿其可能的边缘开始跟踪，也许是通过从堆栈中推入和弹出可能性运行时间，与Kruskal算法相比，这是微不足道的。 您需要更快的东西吗？