算法可视化
数据结构
最小生成树 Kruskal
把所有边按权重从小到大排序,从最小的开始:不成环就加入生成树,成环就跳过(并查集判断)。
main.cpp第 2 行
1// Kruskal: 边按权排序, 从最小开始, 不成环就加入
2sort(edges, edges + m, 按权从小到大);
3for (每条边 e) {
4 if (find(e.u) != find(e.v)) { // 不成环
5 union(e.u, e.v);
6 mst += e.w; // 加入生成树
7 }
8}
9// MST 总权 = 13
变量表2 个变量
mst0
已选边数0
图(节点 + 边)
1/16
所有边按权重排序:1, 2, 3, 4, 5, 6, 7
1 / 16