algorithm - 在 Kruskal 算法中存储路径信息

Question

我已经使用 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
----------------------------------------------------

Answer 1

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

1. 以生成的结构具有的方式定向边缘每个节点最多一个父节点。怎么做？只需选择一个节点并将其设为根。它的 child 是一级节点等
2. 现在以 child->parent 格式存储结果图(在您的表中，您可以将 Loc1 列设为子列，将 Loc2 列设为父列。按子索引)
3. 对于给定的两个节点 a 和 y，需要计算它们的距离，找到它们的父集并查看它们相交的位置。前任。如果 x 的父级是 A，则 A 的父级是 B...父级路径是 ABCDLMN(其中 N 是根)。同样，如果 y 的父根是 EFLMN。如您所见，两者的最小公共(public)根是 L。x->L 的距离为 5，y->L 为 3，=> x 和 y 之间的距离为 5+3=8。

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