最小生成树

[Ir1d]

https://oi-wiki.org/graph/mst/

[XOFee31]

grass

[hanyixuanten]

赞同

[cppyak]

Boruvka 的中文算法描述好像有错。
如果某个边 (u,v) 属于某个连通块，并且权值更小，需要做个更新。

[cppyak]

是写了的。我没看到。抱歉。

[cqbz-ljh]

Boruvka 算法 这里不一定要求权值各不相同啊

[SKHUO]

最小瓶颈生成树有个 $O(n)$ 的随机化算法，国内资料极少（一篇文章都没找到），有会的朋友建议补充一下（我已经不会了）。应该出自高德纳的《计算机程序设计艺术》。

[SKHUO]

upd：找到一篇 https://www.cnblogs.com/degage/p/9740739.html，好像很简单（我印象里很神仙，可能因为我学的时候还不会线性找 k 小值）

[Wang-Yile]

Boruvka 算法如果边权相同，可以以点权作为选择的第二关键字，保证树唯一。

[algo-is-my-GF]

kruskal 算法证明中“一定只有一条”是不是错了
我看 cp-algo 中类似的证明中说的是至少存在一条边 $f$

[Sqrt404]

呃啊啊啊根本看不懂伪代码
（我太菜了）

[sunhaoming665]

……

[zhangbo1000]

当边权为整数时，可以用基数排序加按秩合并并查集优化 Kruskal 算法至 $O(n\alpha(n))$

[lpx0228]

为什么prim不放暴力的代码？只放了堆优化的。