最小生成树

一、定义与性质

• 生成树：连通图的极小连通子图，包含图中所有顶点，只有 $n-1$ 条边
• 最小生成树（MST）：边权之和最小的生成树
• 最小生成树可能不唯一；若边权互不相同则唯一
• $n$ 个顶点的 MST 恰有 $n-1$ 条边

二、Prim 算法（加点法）

从某个顶点开始，每次选择与当前树相连的最小权边，将新顶点加入树中。

void Prim(MGraph G, int v0) {
    int lowcost[MaxVertexNum];  // 到生成树的最小距离
    int adjvex[MaxVertexNum];   // 最小边的另一端
    for (int i = 0; i < G.vexnum; i++) {
        lowcost[i] = G.edge[v0][i];
        adjvex[i] = v0;
    }
    lowcost[v0] = 0;
    for (int i = 1; i < G.vexnum; i++) {
        int min = INF, k = -1;
        for (int j = 0; j < G.vexnum; j++)
            if (lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; k = j; }
        printf("(%d, %d)\n", adjvex[k], k);
        lowcost[k] = 0;
        for (int j = 0; j < G.vexnum; j++)
            if (G.edge[k][j] < lowcost[j]) { lowcost[j] = G.edge[k][j]; adjvex[j] = k; }
    }
}

时间复杂度 $O(|V|^2)$，适合稠密图。

三、Kruskal 算法（加边法）

每次选择权值最小且不构成环的边加入生成树。

typedef struct { int u, v, w; } Edge;

void Kruskal(Edge edges[], int n, int e) {
    Sort(edges, e);                // 按权值排序
    int UFSets[MaxSize]; Init(UFSets, n);
    int count = 0;
    for (int i = 0; i < e && count < n-1; i++) {
        int u = edges[i].u, v = edges[i].v;
        if (Find(UFSets, u) != Find(UFSets, v)) {
            printf("(%d, %d)\n", u, v);
            Union(UFSets, u, v);
            count++;
        }
    }
}

时间复杂度 $O(|E|\log|E|)$（主要取决于排序），适合稀疏图。

四、Prim vs Kruskal

例 1：Prim（从 A 开始）

MST 边：(A,D)=1, (D,C)=4, (C,B)=3, (B,E)=2，总权值 10。

例 2：Kruskal

边按权排序：(A,D)=1, (B,E)=2, (B,C)=3, (C,D)=4, (A,C)=5, (D,E)=5, (A,B)=6, (C,E)=6。

依次选 (A,D)、(B,E)、(B,C)、(C,D)，已 4 条边（$n=5$）停止。总权值 10。