图的最小生成树

基本概念

图的最小生成树问题在现实生活中有重要应用，譬如在 n 个城市之间搭建通信网。
对于 n 个节点的连通图，可以建立很多不同的生成树，每个生成树都可以是一个通信网，要是通信网总的耗费最小（衡量标准根据具体情况而定，可能是距离、价格等等），就是要找到一棵最小生成树，这就是最小生成树问题(Minimum Cost Spanning Tree, MST)。一棵生成树的代价就是各边的代价之和。

算法原理

构造生成树有很多算法，多数算法都用到一条 MST 的性质：

假设 N = (V, {E}) 是一个连通网，U 是顶点集 V 的一个非空子集，如果 (u, v) 是一条具有最小权值（代价）的边，其中 u∈U, v∈V-U，那么一定存在一棵包含边 (u, v) 的最小生成树。

该性质可以用反证法加以证明。

普利姆算法(Prim)

算法过程

假设 N = (V, {E}) 是连通网，TE 是 N 上最小生成树中变得合集。
算法从 U = {u₀}(u₀∈V), TE = {} 开始，重复如下操作：
在所有 u∈U, v∈V-U 的边 (u, v)∈E 中找一条代价最小的边 (u₀, v₀) 并入集合 TE，同时 v₀ 并入 U ，直至 U=V 为止。
此时 TE 中必有 n-1 条边，则 T = (V, {TE}) 为 N 的最小生成树。

为了实现算法，需要一个辅助数组 closedge，用来记录从 U 到 V-U 具有最小代价的边。
对每个顶点 v_i∈V-U，在辅助数组中存在一个分量 closedge[i]，它包含两个域，
其中 lowcost域 存储该边上的权，vex 域 存储该边依附在 U 中的顶点。

算法实现（邻接矩阵）

// Prim
void MiniSpanTree_Prim(MGraph *G, VertexType v)
{
    int i, j, k;
    ArcType minicost;
    // 定义辅助数组，记录当前最小生成树与树外节点的最小距离及关联的树内顶点
    struct {
        VertexType adjvex; // 用于复原
        ArcType lowcost;
    }closedge[MAX_VERTEX_NUM];

    // 初始化 closedge
    k = LocateVex(G, v);
    for (i = 0; i < G->vexnum; ++i)
    {
        if (G->vexs[i] == v)
            closedge[i].lowcost = 0;
        else
        {
            closedge[i].adjvex = v;
            closedge[i].lowcost = G->arcs[k][i];
        }
    }

    // Prim 算法运行 G->vexnum -1 次
    for (i = 1; i < G->vexnum; ++i)
    {
        // 计算最小，得到k，k为最顶距离对应的节点（位置下标）
        minicost = INF;
        for (j = 0; j < G->vexnum; ++j)
        {
            if (closedge[j].lowcost != 0 && closedge[j].lowcost < minicost)
            {
                minicost = closedge[j].lowcost;
                k = j;
            }
        }
        printf("%c-[%d]-%c\t", closedge[k].adjvex, G->arcs[LocateVex(G, closedge[k].adjvex)][k], G->vexs[k]);
        // 将节点 G->vexs[k] 纳入生成树
        closedge[k].lowcost = 0;
        // 更新 closedge
        for (j = 0; j < G->vexnum; ++j)
        {
            if (G->arcs[k][j] < closedge[j].lowcost)
            {
                closedge[j].adjvex = G->vexs[k];
                closedge[j].lowcost = G->arcs[k][j];
            }
        }
    }
}

复杂度分析

算法实现中有两个内循环，第 1 个内循环是在 closedge 中选择 lowcost 最小值，时间为 O(n-1)；
第 2 个内循环更新 closedge 中的 lowcost 和 vex，时间为 O(n)。

因此，普利姆算法时间复杂度为 O(n²)，与图的顶点数有关，而与图中的边数无关，所以适用于求 边稠密 的网的最小生成树。

克鲁斯卡尔算法(Kruskal)

算法过程

普利姆从顶点角度建立最小生成树，而克鲁斯卡尔算法则从边的角度求解。

假设连通网 N = (V, {E})，则令最小生成树的初始状态为 只有 n 个顶点而无边的非连通图 T = (V, {})，网中每个顶底啊都自成一个连通分量，在 E 中选择代价最小的边，如果该边依附的顶点落在 T 中不同的连通分量中，则将此边加入到 T 中，否则舍去选择下一条代价最小的边。
依此类推，直到 T 中所有顶点都在同一个连通分量上为止。

连通分量可以用 并查集 MFSet 来表示，每一轮选择最小代价的边可以用 堆 来实现。

算法实现（邻接矩阵）

// Kruskal
void MiniSpanTree_Kruskal(MGraph *G)
{
    // k 用于取当前权值最小边
    // m, n 用于取顶点所在的连通分量
    int i, k = G->arcnum, m, n;
    int AS[MAX_VERTEX_NUM]; // 用并查集表示连通分量
    ArcHeap AH[MAX_VERTEX_NUM]; // 用边集堆选择最小权值边
    InitMFSet(AS, G->vexnum);
    InitArcHeap(AH, G->arcs, G->arcnum, G->vexnum);

    for (i = 0; i < G->arcnum; ++i)
    {
        k = GetRoot(AH, k);
        m = Fix_MFSet(AS, AH[k].vex_1);
        n = Fix_MFSet(AS, AH[k].vex_2);
        // 属于不同的连通分量，将其加入
        if (m != n)
        {
            // 合并连通分量
            Mix_MFSet(AS, m, n);
            printf("%c-[%d]-%c\t", G->vexs[AH[k].vex_1], G->arcs[AH[k].vex_1][AH[k].vex_2], G->vexs[AH[k].vex_2]);
        }
        --k;
    }
}

复杂度分析

算法实现中至多对 e 条边各扫描一次，用堆来存放边，则每次选择除最小代价的边仅需要 O(loge) 的时间（第一次为 O(e)）；
网中的连通分量是等价类，用并查集来描述，构造并查集需要 O(eloge) 的时间。

因此，克鲁斯卡尔算法时间复杂度为 O(eloge)，与图的顶点数无关，而与图的边数有关，所以适用于求 边稀疏 的网的最小生成树。

完整代码可参见：GitHub

DONE！

上篇: 图的关节点问题下篇: 有向图的强连通分量

基本概念
算法原理
普利姆算法(Prim)
克鲁斯卡尔算法(Kruskal)