Kruskal解决最小生成树问题
Kruskal解决最小生成树问题
- 问题
给定一个有若干边和顶点构成的图，从中选则部分边构成树，且树的权值要最小。 - 解析
- 设计
Void Kruskal（MGraph）
{ T ={}
While（T中不到n-1条边&&E中还有边）
{从E中抽取一条权值最小的边
将E（s，e）从E中删除；
If（E（s，e）不在T中构成回路）
将E加入T
Else
继续循环
}
} - 分析
O(ElogE) - 源码
https://github.com/CunHua-YYT/CunHua-YYT/blob/master/Kruskal.cpp