前言
说到最小生成树（Minimum Spanning Tree），首先要对以下的图论概念有所了解。
图
图（Graph）是表示物件与物件之间的关系的数学对象，是图论的基本研究对象。图的定义方式有两种，其一是二元组定义。图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。
边的方向
边是有方向的，单方向（如只允许从点a到达点b）的边称为单向边或有向边；允许双方互达的边称为双向边或无向边。包含单向边的图称为单向图，不包含单向边的称为无向图。
带权图
图上的边或者点都可以带有权值，带权值的图就称为带权图。
子图
任取图G的若干点，以及这些点在G中存在的若干边构成的集合称为G的子图。
连通图
如果无向图G的任意点都可以直接或间接地到达其余所有点，那么G就称为连通图。
树
| 树是一种特殊的图，树上的所有点与其他点之间有且仅有一条直接或间接路径。性质： | V | = | E | +1。 |
生成树
如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。显然对于同一个图，生成树并不唯一。
最小生成树
定义
图G的最小生成树（假设存在）是边权和最小的生成树。
算法
Prim和Kruskal
Prim
Prim又称加点法。
步骤
- 在G中任意选取一个结点$v_1$，置$V’={v_1}，E’=\empty，k=1$
- 在$V-V’$中选取与某个$v_i ∈V’$邻接的结点$v_j$ ，使得边$(v_i , v_j)$权值最小，置$V’=V’∪{v_j }，E’=E’∪{(v_i ,v_j )}，k=k+1$
-
重复第二步，直到$k= V $
复杂度
\[O(\mid V\mid^2)\]模板
// cost 0~n-1
// 不连通 return -1
const int INF = 0x3f3f3f3f;
const int MAXN = 110;
bool vis[MAXN];
int lowc[MAXN];
int Prim(int cost[][MAXN], int n) {
int ans = 0;
memset(vis, false, sizeof(vis));
vis[0] = true;
for (int i = 1; i < n; i++)
lowc[i] = cost[0][1];
for (int i = 1; i < n; i++) {
int minc = INF;
int p = -1;
for (int j = 0; j < n; j++) {
if (!vis[j] && minc > lowc[j]) {
minc = lowc[j];
p = j;
}
}
if (minc == INF) {
return -1;
}
ans += minc;
vis[p] = true;
for (int j = 0; j < n; j++) {
if (!vis[j] && lowc[j] > cost [p][j]) {
lowc[j] = cost[p][j];
}
}
}
return ans;
}
Kruskal
Kruskal又称加边法。
步骤
- 在G中选取最小权边$e_1$，置$i=1$
- 当$i=n-1$时，结束，否则进行下一步
- 设已选取的边为$e_1,e_2,…,e_i$，在G中选取不同于以上的边$e_i+1$，使得{$e_1 ,e_2,……, e_i , e_i+1$}中无回路且$e_i+1$是满足此条件的最小权边。
- 置$i=i+1$，转第二步
复杂度
\[O(\mid E\mid \log \mid E \mid)\]模板
const int MAXM = 10000; // 边
const int MAXN = 110; // 点
int F[MAXN]; // 并查集
struct Edge {
int u, v, w; // 起点、终点、权值
}edge[MAXN];
int tol; // 边数，加边算法，初始为零
void AddEdge(int u, int v, int w) {
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
}
bool CMP(Edge a, Edge b) {
return a.w < b.w;
}
int Find(int x) {
return x == F[x] ? x : F[x] = Find(x);
}
// n 为图的点总数
int Kruskal(int n) {
memset(F, -1, sizeof(F));
sort(edge, edge + tol, CMP);
int cnt = 0, ans = 0;
for (int i = 0; i < tol; i++) {
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int t1 = Find(u);
int t2 = Find(v);
if (t1 != t2) {
ans += w;
F[t1] = t2;
cnt++;
}
if (cnt == n - 1) {
break;
}
}
return cnt < n - 1 ? -1 : ans;
}