UVa 10034 - WinDaLex/Programming GitHub Wiki

Freckles

from Volume 7. Graph Algorithms and Implementation Techniques

Description

求直角坐标系上能够把几个点相连起来最短线段的长度。输入每个点的坐标。输出最短线段的长度。

Solution

经典的最小生成树的题目。求最小生成树的两种算法——Kruskal 和 Prim。设图 G 中点数为 n ，边数为 e 。Kruskal 的时间复杂度为 O(e log e) ，取决于对边的排序效率。要求存储每条边，可用并查集优化（由于并查集优化后代码更短，效率更高，因此默认都用并查集优化后的 Kruskal。Prim 的时间复杂度是比较多变，取决于图的存储结构，和是否采用二叉堆（优先队列）优化。未优化的时间复杂度为 O(n^2) ，适合于稠密图。而是堆优化过后，时间复杂度达到O(e log n)，不过相比Kruskal属于费力不讨好。除非利用 Fibonacci 堆优化，可以达到 O(n log n) 。Fibonacci堆 优化的实现较难（反正我不懂），所以在 ACM 中，大都采用 Kruskal 的方法求最小生成树的路径长度。