什么是最小生成树
三点：
- 是一棵树，
无回路
|V|个顶点，一定有|V-1|条边 - 生成树
包含全部顶点
|V|-1条边都在图中
（向生成树中任意加一条边就会产生回路了）
如图,第一个是完全图。其他三个是其生成树。
Paste_Image.png
- 边的权重和最小
充分必要：
最小生成树存在 = 图联通
贪心算法
贪：一步一步解决，但是每一步都是眼前最好的。
这个问题中，什么是好：权重小的边
#约束条件：
{
只能用图里有的边
只能正好用掉|V|-1条边
不能有回路
}
prim 算法
Prim算法：
从一个根节点，让一棵小树，慢慢长大
void Prim(){
MST={s};//一棵最小生成树
while(1){
V=未收录顶点中dist最小者；//dist 是V 到整个集合的距离。
if(这样的V不存在)
return;
将V收录进 MST：dist[V]=0
for(V 的 邻接点 W){
if(dist[W]!=0)//未收录
if( E(V,W） < dist[W]){
dist[W] = E(V,W);
parent[W] = V;
}
}
}
if(MST 中收的顶点 数 <|V| ){
Error("图不连通，生成树不存在")
}
}
T=O(|V|*|V|)
适合 稠密图
#BB
有点和dijkstra 算法相似，
不过它选点的时候，选下一个点，距离该集合最近的点。
dijkstra选的是：距离 源点 S 最近的点。
Paste_Image.png
Kruskal 算法
把森林合成一棵树
void Kruskal(Graph G){
MST={}
while(MST 中不到|V|-1 条 && E中还有边存在){
从E 中取一条权重最小的边E(V,W);/*适用最小堆来存储*/
将E(V,W)从E中删除
if(E(V,W) 不在MST中构成回路)/*并查集*/
将E(V,W)加入MST;
else
无视E(V,W)
}
if(MST 边 < |V|-1 条){
Error（"不连通，生成树不存在"）
}
}
T=O(|E|log|E|)
其中log|E|是 最小堆和并查集
演示图
最小生成树一定唯一么？
不一定。
Paste_Image.png
