生成两个节点之间的边数
我使用 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
----------------------------------------------------
I generated this Minimum Spanning Tree using Kruskal algorithm and I have a hard time generating paths between two nodes. Can someone help me with pseudocode? I tried using Adjacency List and Adjaceny matrix
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
----------------------------------------------------
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您只想要两个节点之间的任何路径，则 广度优先搜索 就可以了，并且会生成最短路径（因为它是最小生成树）。
If you just want any path between two nodes, a Breadth First Search would do, and would generate the shortest path (because its a minimum spanning tree).
根据定义，生成树没有循环（或循环），因此两个节点之间最多只能有一条路径（即不是“路径”，复数）。
也许我不明白这个问题。您是否想找出树中两个给定节点的连接方式？
如果是这样，在我看来，这听起来像是最简单的蛮力，你只需从一个点沿着其可能的边缘进行跟踪，也许通过从堆栈中推入和弹出可能性，将是最坏情况的 O(Edges) 运行时间，与克鲁斯卡尔算法相比，这微不足道。
您需要更快的东西吗？
Spanning trees, by definition, have no cycles (or loops), so at most you can only have one path (i.e. not "paths", plural) between two nodes.
Perhaps I'm not understanding the question. Are you trying to find how two given nodes are connected in your tree?
If so, it sounds to me like the simplest brute force on this, where you would just follow from one point along its possible edges, perhaps by pushing and popping possibilities from a stack, would be worst-case O(Edges) run time, which would be trivial compared to Kruskal's Algorithm.
Do you need something faster?