0

我使用 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
----------------------------------------------------
4

1 回答 1

2

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

  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 为单位）。

于 2012-02-21T19:39:16.870 回答