其实我在学最短路之前就学了生成树了，现在接着写。

本文介绍2种算法：Kruskal，Prim

PS:文中分大小写。 图为G(V,E)，V为节点集合，E为边集合，但v表示某个节点（v∈V）

其实很多都和最短路差不多的，松弛操作不同而已。

前提：连通图

Kruskal:

• 原理： 通过排序每一条边（权值递增）从|E|条边中取V-1条边出来（V个点嘛，最小生成树始终是V-1条边的），满足每次选的边的起点和终点不在一棵树上。
• 采用： 并查集
• 步骤：
  1. 初始化边，并以升序排序
  2. 初始化并查集，这里以p域代表， p[i]=i; // i∈[1,|V|]
  3. 循环（1~|E| : i）
     1）判断第i条边的起点和终点是否在一棵树上（使用并查集，可保证非常快的判断）
     2）如果不在的话，加入i边，并使得p[起点]=终点 或 p[终点]=起点

并查集实现：

inline int find(int x){	int t = x;	while(p[x] != x) x = p[x];	p[t] = x;	return x;}

• 分析：时间复杂度O(E) 并查集的时间太小 省略。
• 适用于：任何连通图 稀疏图
• 优化：我不会

Prim:

• • 原理：通过|V|-1次加入树中与v的边, min{key[v] | v∈G-已生成的最小树} 到最小树中，来实现最小生成树
  • 采用：优先队列 priority_queue (#include <queue> 要定义一个比较类来实现最小堆)
  • 步骤：
    1. 初始化key域 key[i] = INF; // i∈[1,|V|]
    2. key[S]=0； // S为最小生成树的根
    3. 初始化vis域（已生成树），且vis[i]=0; // i∈[1,|V|]
    4. 将S压入优先队列q
    5. 循环（q不为空）
       1）使u=q的队头，并将队头出队
       2）把u与树中的边加入到树中，即设置u已经在树中vis[u]=1;
       3）对以u为起点的边进行伪松弛（这些边的终点一定是不在树中的，即vis[a]!=1）。并把这些边的终点压入队列。

我说的伪松弛的指的是：if(key[i] > edge[u][i]) key[i] = edge[u][i];//注意，如果没有u->i这条路径，edge[u][i]一定要是INF,不要是0，这点在初始化时做

（如果初始化为0的话，可以这样 if(edge[u][i] && key[i] > edge[u][i]) key[i] = edge[u][i];）

（之所以叫伪松弛，因为这和松弛太像了。）

• 分析：时间复杂度O(KV) K为优先队列解压最小的实现
• 优化：优化堆的实现（不嫌麻烦就手打FIB堆。。优先队列是用二叉堆的。）

//好像漏洞百出，以后再来更新，欢迎大家帮忙找漏洞，欢迎吐槽