-1

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

Loc1 |  Loc2 |  Distance
  02 |   10  |    2.00 Km
  05 |   07  |    5.39 Km
  02 |   09  |    5.83 Km
  04 |   05  |    5.83 Km
  06 |   08  |    5.83 Km
  03 |   09  |    7.07 Km
  01 |   04  |    11.18 Km
  07 |   09  |    11.18 Km
  07 |   08  |    15.81 Km
Total Weight = 70.12 Km
----------------------------------------------------
4

2 回答 2

1

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

于 2012-02-22T05:05:31.747 回答
0

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

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

如果是这样，对我来说这听起来像是最简单的蛮力，您只需沿着其可能的边缘从一个点开始，也许通过从堆栈中推送和弹出可能性，将是最坏情况的 O(Edges) 运行时间，与克鲁斯卡尔算法相比，这将是微不足道的。你需要更快的东西吗？

于 2012-02-22T05:04:43.647 回答