algorithm - 在图中制作成本矩阵

Question

问题:

形成一个网络，即所有基地应该从每个基地可达。如果有一条连接基地的隧道路径，则可以从另一个基地到达一个基地。假设基于具有整数坐标的二维平面。在两个基地之间 build 隧道的成本是坐标 (x1,y1) 和 (x2,y2) 是 min{ |x1-x2|, |y1-y2| }.

形成网络的最低​​成本是多少。

1 ≤ N ≤ 100000   // Number of bases
-10^9 ≤ xi,yi ≤ 10^9

典型的Kruskal 最小生成树 实现。但是您不能存储 (10^5)^2 条边。那么我应该如何制作我的成本矩阵，如何制作图表以便我可以应用 Kruskal 算法？

Answer 1

您不应该存储整个图表，因为您实际上并不需要它。事实上在这种情况下我认为Prim's算法更适合这种情况。您不会在任何时候都需要所有边，而是在每次迭代中更新大小为 N 的最小距离数组。当然，复杂性仍将按 N**2 的顺序排列，但至少内存不会成为问题。您还可以进一步使用计算距离的特定方式来提高复杂性(使用一些有序结构来存储点)。