土法炼钢 · 系统与基础设施

最小生成树：割性质、Kruskal/Prim/Borůvka 与线性时间开放问题

2026-06-05 | algorithms | #mst #kruskal #prim #boruvka #union-find #cut-property #fibonacci-heap #karger-klein-tarjan #chazelle

从允许并列边的割性质与环性质出发，给出 Kruskal、Prim、Borůvka 的正确性条件与分步图，用可复现程序按比较次数、decrease-key 次数和计时对比三者，并梳理从 1926 年到 Chazelle、Pettie–Ramachandran 的谱系与确定性线性时间开放问题。