克鲁斯卡尔算法 (加边法)
G(V, E) 带权连通无向图
(1), 将 G 中的边按权值从小到大依次选取,若选取的边使生成树不构成回路,并入 TE 中。
(2), 从剩下的边中选取边,执行操作 (1), 如此进行下去,直到 TE 中包含 n-1 条边为止,此时的T,此时的 T ,即为最小生成树。
Kruskal 的实现需要用到并查集。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
阅读(556) | 评论(0) | 转发(0) |