图的最小生成树
最小生成树：包含图的所有n个顶点，且有足以构成一个连通图的（n - 1）条边的极小连通子图。 但满足上述条件的极小连通子图不一定是最小生成树。
下述两个算法用于求无向图的最小生成树。有向图的最小生成树称为最小树形图，此处不做讨论。
Prim普里姆算法
Prim算法，也叫“加点法”,通过从一个结点连接到下一个结点的方式寻找图的最小生成树。
算法步骤
- 将图中所有结点分成AB两类，A表示已包含在树中的，B表示还没包含在树中的；
- 任选一个结点加入A中，作为起始点；
- 在B中所有结点中找到到A中结点的边权值最小的结点，并将其移到A中；
- 直到B中没有结点，此时A中包含的所有结点和走过的所有边就构成图的最小生成树。
辅助数据结构
辅助数组closedge用于记录从A到B具有最小权值的边。
其中储存的每个元素包含两个域：
lowcost存储最小边的权值， adjvex存储最小边在A中的（那一个）结点。
算法实现（严蔚敏 《数据结构》）
void MiniSpanTree_Prim(AMGraph G, VerTexType u) {
k = LocateVex(G, u); // 定位到u的下标
for(j = 0; j < G.vexnum; j++)
if(j != k) closedge[j] = {u, G.arcs[k][j]}; // 初始化为到A中结点的边信息
closedge[k].lowcost = 0;
for(i = 1; i < G.vexnum; i++) {
k = Min(closedge); // closedge[k]存的是当前最小边
u0 = closedge[k].adjvex; v0 = G.vexs[k];
cout << u0 << " " << v0; // 分别为最小边的两个结点
closedge[k].lowcost = 0; // 第k个结点并入A
for(j = 0; j < G.vexnum; j++) // 并入后找新的最小边
if(G.arcs[k][j] < closedge[j].lowcost)
closedge[j] = {G.vexs[k], G.arcs[k][j]};
}
}
算法分析
第一个循环（初始化）时间复杂度O(n)；
第二个循环遍历其余(n-1)个结点，时间复杂度O(n)；
第二个大循环有两个内循环，一个是求当前最小边，一个是并入新结点后，重新寻找最小边。
所以时间复杂度为O(n²)。
与图的边数无关，适用于处理稠密图。
Kruskal克里斯卡尔算法
Kruskal算法，也叫“加边法”，通过逐步增加生成树的边来求得最小生成树。
算法步骤
- 初始化：将图中所有边按从小到大排序，可以认为每个顶点各自形成一个连通分量；
- 选择图中最小的边，如果此边的顶点不与已经有的部分生成树形成回路，就把这条边加入；否则舍弃这条边，选择下一个最小的边；
- 重复第二步，直到图中所有结点都位于同一连通分量上，就得到了最小生成树。
辅助数据结构
- 结构体数组Edge：存储边的起点终点和权值。
struct {
VerTexType Head, Tail;
ArcType lowcost;
} Edge[arcnum];
- Vexset[i]：标记各结点所属的连通分量。
初始时Vexset[i] = i，表示各个结点各成一个连通分量。
算法实现
void MiniSpanTree_Kruskal(AMGraph G) {
Sort(Edge);
for(i = 0; i < G.vexnum; i++) Vexset[i] = i;
for(i = 0; i < G.vexnum; i++) {
v1 = LocateVex(G, Edge[i].Head), v2 = LocateVex(G, Edge[i].Tail);
vs1 = Vexset[v1], vs2 = Vexset[v2];
if(vs1 != vs2) {
cout << Edge[i].Head << " " << Edge[i].Tail;
for(j = 0; j < G.vexnum; j++)
if(Vexset[j] == vs2) Vexset[j] = vs1;
}
}
}
算法分析
最耗时的循环是合并两个连通分量。
时间复杂度是O(elog2(e))，与边数相关。适合处理稀疏图。