Kruskal 中应用

一句话理解

Kruskal 用并查集判断边的两端是否已连通。

为什么要学

最小生成树。

讲解

边按权排序，不形成环就加入。并查集判环：已同一集合则会成环。

例子

从小到大加边，连通则跳过。

常见错误

• 先加边再判。
• 有向图套 Kruskal。