二维百万点集最小生成树（最小点距和）算法异常原因及优化咨询

你要解决的是1e6个二维平面点的最小总距离连通问题，本质是求欧几里得最小生成树（EMST），你观察到排序顺序影响结果的原因以及优化方案如下：

排序顺序导致结果不一致的成因 #

1. 你的现有算法没有全局最优的贪心保证：你设计的逻辑是只要起点p1未访问就连通它和最近邻，排序顺序决定了边的选择优先级：
   • 按距离升序排序时，你会优先选短边，更接近最小生成树的选边逻辑
   • 按距离倒序排序时，你会优先选长边，自然会得到总长度更大的边集合
2. 访问标记逻辑存在缺陷：你仅用visited字典标记点是否被访问过，没有做环检测、也没有维护连通分量关系。如果某个点的最近邻已经属于另一个连通分量，你的逻辑会直接跳过这条可能的跨分量连边，最终不仅结果会随排序顺序变化，甚至可能出现多个孤立连通分量，无法做到全连通。
3. 额外的代码bug：你写的visited[(x1,y1)] +=1语句在键不存在时会直接抛出KeyError，因为你没有对首次出现的点做初始化赋值。

算法优化方案 #

针对1e6量级的平面点，普通的Prim/Kruskal算法（针对完全图）复杂度太高无法运行，需要结合欧几里得最小生成树的特性优化：

核心优化思路 #

欧几里得最小生成树的所有边都属于点集的Delaunay三角剖分的边集，而Delaunay三角剖分的边数是O(n)量级（1e6个点大概对应300万条边），完全在可处理范围内。

具体优化步骤 #

1. 替换visited字典为**并查集（DSU）**数据结构：支持O(α(n))复杂度的连通性判断和连通分量合并，用来避免选边时产生环，同时保证跨分量的边能被正确选中。
2. 生成点集的Delaunay三角剖分，提取所有三角边作为候选边，不需要自己遍历所有点找最近邻，效率更高也不会漏选必要的边。
3. 对所有候选边按长度升序排序，用Kruskal算法遍历：如果边的两个端点属于不同连通分量，就保留这条边、合并两个连通分量，直到所有点属于同一个连通分量，此时得到的边集合就是总距离最小的连通方案。

备选轻量方案 #

如果你不想引入Delaunay三角剖分的实现，可以用优化版的Prim算法：用优先队列维护每个点到当前生成树的最小距离，每次选距离最小的点加入生成树，同步更新相邻点的最小距离，整体复杂度为O(nlogn)，也能得到正确的最小生成树。

内容的提问来源于stack exchange，提问作者Python Newbie