在克鲁斯卡尔算法中存储路径信息

Question

我已经使用克鲁斯卡尔算法生成了最小生成树，我想知道如何存储路径

这是我的最小生成树

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
----------------------------------------------------

Answer 1

这取决于您有多少额外空间。假设您需要节省空间：

1. 以最终结构的方式定位边缘
   每个节点最多有一个父节点。怎么做呢？只需选择一个节点并将其设为根即可。它的子节点是第一级节点等
2. 现在以子节点->父节点的格式存储结果图（在表中，您可以将 Loc1 列设为子节点，将 Loc2 列设为父节点。按子节点对其进行索引）
3. 对于给定的两个节点 a 和 y，其需要计算距离，找到它们的父集并查看它们相交的位置。前任。如果 x 的父级是 A，A 的父级是 B...父级路径是 ABCDLMN（其中 N 是根）。类似地，如果 y 的父根是 EFLMN。正如你所看到的，它们的最小公共根是L。x->L的距离是5，y->L是3，=>L。 x和y之间的距离是5+3=8。

复杂度：O(hlogn)，其中 h 是树的高度，n 是树中元素的数量（我假设每个节点的查找时间为 logn）。