我已经用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
----------------------------------------------------
最佳答案
这取决于你有多少额外的空间假设您需要节省空间：
调整边的方向，使生成的结构
每个节点最多有一个父节点怎么做只需选择一个节点并使其成为根节点它的子节点是一级节点等
现在以child->parent格式存储结果图（在表中，可以将loc1列设为child，将loc2列设为parent）。按子索引）
对于给定的两个节点，需要计算其距离的a和y，找到它们的父集并查看它们的相交处如果x的父母是A，A的父母是B父路径是ABCDLMN（其中N是根）类似地，如果y的父根是EFLMN如你所见，它们的最小公共根都是L。距离x->L是5，y->L是3，=>距离x和y是5+3=8。
复杂性：O（HLogn），其中H是树的高度，N是树中元素的数量（我假设登录时每个节点的查找时间）。
关于algorithm - 在Kruskal算法中存储路径信息，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9383121/