在Kruskal算法中存储路径信息

Question

我已经使用Kruskal算法生成了最小生成树，我想知道如何存储路径

这是我的最小生成树 通用标签

Answer 1

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

1. 对边缘进行定向，使所得结构在 每个节点最多有一个父节点。怎么做？只需选择一个节点并使其成为根即可。它的孩子是一级节点等等
2. 现在将结果图形存储为child-> parent格式（在表中，您可以将Loc1列作为子代，将Loc2列作为父代。按子代对其进行索引）
3. 对于需要计算距离的给定两个节点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是树中元素的数量（我假设logn中每个节点的查找时间）。