一、什么是最小生成树

对于一个带权连通无向图 G=(V,E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能图同。设 R 为 G 的所有生成树的集合，若 T 为 R 中边的权值之和最小的生成树，则 T 称为 G 的最小生成树（Minimum-Spanning-Tree, MST）。

最小生成树（Minimum Spanning Tree）是一颗树，它无回路，\(|V|\) 个顶点一定有 \(|V| -1\) 条边。它是一个生成树，包含全部顶点，\(|V| -1\) 条边都在图里。并且，最小生成树边的权重和最小。最小生成树存在，则图一定联通；图联通的话，一定可以找到最小生成树。

最小生成树可能有多个，但边的权值之和总是唯一且最小的；

最小生成树的边数 = 顶点树 - 1。砍掉一条边则不连通，增加一条边会出现回路；

如果一个连通图本身就是一棵树，则其最小生成树就是它本身；

只有连通图才有生成树，非连通图只有生成森林；

二、贪心算法

解决最小生成树问题，可以使用贪心算法。贪心算法分阶段地工作，在每一个阶段，可以认为所做决定是好的，而不考虑将来的后果。一般来说，这意味着选择的是某个局部的最优。当算法终止时，我们希望局部最优就是全局最优。如果是这样的话，那么算法就是正确的；否则，算法得到的是一个次优解（suboptimal solution）。如果不要求绝对最佳答案，那么又是会用简单的贪心算法来生成近似答案，而不是使用一般产生准确答案所需要的复杂算法。

贪心算法要求每一步都是最好的，即权重最小的边。最小生成树要求我们只能用图中有的边，并且只能正好用到 \(|V| - 1\) 条边，并不能有回路。贪心算法所得到的结果不一定是最优的结果，但是都是相对近似（接近）最优解的结果。

2.1、Prim算法

Prim（普里姆）算法的基本思路是从一个根节点开始，让一颗小树慢慢长大。它从某一个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

设 G=(V,E) 是联通网，T=(U,D) 是最小生成树，V，U 是顶点集合，E，D 是边的集合；
若从顶点 u 开始构造最小生成树，则从集合 V 中取出顶点 u 放入集合 U 中，标记顶点 u 的 visited[u] = 1；
若集合 U 中顶点 \(u_{i}\) 和集合 V-U 中的顶点 \(v_{j}\) 之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点 \(v_{j}\) 加入集合 U 中，将边 \((u_{i},v_{j})\) 加入集合 D 中，标记 \(visited[v_{j}] = 1\);
重复步骤 ②，直到 U 与 V 相等，即所有顶点都被标记为访问过，此时 D 中有 n-1 条边；

/**
 * @brief Prim算法生成最小生成树
 * 
 * @param graph 待操作的图
 * @param vertex 开始的顶点对应的下标
 */
void Prim(Graph graph,int vertex)
{
    int visited[graph->vertexNum];                      // 标记节点是否被访问过
    memset(visited,0,sizeof(visited));

    visited[vertex] = 1;                                // 把当前这个节点标记为已访问
    int v1 = -1,v2 = -1;                                // v1和v2记录两个顶点的下标
    int minWeight = 9999;
    int i = 0, j = 0,k = 0;

    // 因为有graph->vertexNum个顶点，普里姆算法结束后有graph->vertexNum-1条边
    for(k = 1; k < graph->vertexNum; k++)
    {
        // 确定每一次生成的子图，和哪个节点的距离最近
        for(i = 0; i < graph->vertexNum; i++)           // i节点表示被访问过的节点
        {
            for(j = 0; j < graph->vertexNum; j++)       // j节点表示未被访问过的节点
            {
                if(graph->edge[i][j] != 0)
                {
                    if(visited[i] == 1 && visited[j] == 0 && graph->edge[i][j] < minWeight)
                    {
                        // 寻找已经访问过的节点和未访问过的节点间的权值最小的边
                        minWeight = graph->edge[i][j];
                        v1 = i;
                        v2 = j;
                    }
                }
            }
        }
        // 找到一条边最小的
        printf("边<%c,%c>权值：%d\n",graph->vertex[v1],graph->vertex[v2],minWeight);
        // 将当前这个找到的节点标记为已经访问过
        visited[v2] = 1;
        // minWeight重新设置为一个最大值
        minWeight = 9999;
    }
}

时间复杂度为：\(T = O(|V|^{2})\)，适用于边稠密图；

2.2、Kruskal算法

Kruskal（克鲁斯卡尔）算法将森林合并成树；它每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）直到所有节点都连通。

Kruskal 算法需要解决以下两个问题：

对图中的所有边按照权值大小进行排序；
将边添加到最小生成树中，怎么判断是否形成了回路；

问题 1 ，我们可以采用排序算法进行排序即可。问题 2 的处理方式为：记录顶点在“最小生成树”中的终点，顶点的终点是“在最小生成树中与它连通的最大顶点”。然后每次需要将一条边添加到最小生成树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。

/**
 * @brief Kruskal算法
 * 
 * @param graph 待操作的图
 */
void Kruskal(Graph graph)
{
    int i = 0;
    int index = 0;                                                  // 表示最后结果数组的索引
    int ends[graph->edgeNum];                                       // 用于保存“已有最小生成树”中每个顶点在最小生成树中的终点
    memset(ends,0,sizeof(ends));

    Edge result = calloc(graph->edgeNum,sizeof(struct ENode));      // 创建结果数组，保存最后的最小生成树

    Edge edges = GetEdges(graph);                                   // 获取图中所有边的集合
    SortEdge(graph,edges);                                          // 按照边的权值大小进行排序（从小到大）

    // 遍历edges数组，将边添加到最小生成树中，并判断准备加入的边是否形成回路
    // 如果没有，就加入ends数组中
    for(i = 0; i < graph->edgeNum; i++)
    {
        int m = GetEnd(edges[i].v1,ends);                           // 获取v1这个顶点在已有的最小生成树中的终点
        int n = GetEnd(edges[i].v2,ends);                           // 获取v2这个顶点在已有的最小生成树中的终点

        // 判断是否构成回路
        if(m != n)                                                  // 没有构成回路
        {
            ends[m] = n;                                            // 设置m在“已有最小生成树”中的终点
            result[index++] = edges[i];                             // 有一条边加入result数组
        }
    }

    // 统计并打印最小生成树，数组result数组
    for(i = 0; i < index; i++)
    {
        printf("边<%c,%c>权值: %d\n",graph->vertex[result[i].v1],graph->vertex[result[i].v2],result[i].weight);
    }
}

/**
 * @brief 边按权重排序
 * 
 * @param graph 待操作的图
 * @param edges 待排序的边
 */
void SortEdge(Graph graph, Edge edges)
{
    int i = 0, j = 0;
    Edge temp = malloc(sizeof(struct ENode));

    for(i = 0; i < graph->edgeNum-1; i++)
    {
        for(j = 0; j < graph->edgeNum-1-i; j++)
        {
            if(edges[j].weight > edges[j+1].weight)
            {
                *temp = edges[j];
                edges[j] = edges[j+1];
                edges[j+1] = *temp;
            }
        }
    }
}

/**
 * @brief 获取图中的边
 * 
 * @return Edge 返回边的数组
 */
Edge GetEdges(Graph graph)
{
    int index = 0;
    Edge edges = calloc(graph->edgeNum,sizeof(struct ENode));

    for(int i = 0; i < graph->vertexNum; i++)
    {
        for(int j = i+1; j < graph->vertexNum; j++)
        {
            if(graph->edge[i][j] != 0)
            {
                Edge edge = malloc(sizeof(struct ENode));
                edges[index].v1 = i;
                edges[index].v2 = j;
                edges[index].weight = graph->edge[i][j];
                index++;
            }
        }
    }

    return edges;
}

/**
 * @brief 获取下标为i的顶点的终点
 * 
 * @param i 表示传入顶点对应的下标
 * @param ends 数组记录了各个顶点的对应的终点是哪个，ends数组在遍历过程中逐步形成
 * @return int 返回的就是i为i的对应终点的下标，如果没有就返回自己的下标
 */
int GetEnd(int i,int ends[])
{
    while(ends[i] != 0)
    {
        i = ends[i];
    }

    return i;
}

时间复杂度为：\(T = O(|E| log|E|)\)，适用于边稀疏图；

2.3、测试程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    int i = 0,j = 0,k = 0;
    char data[] = {'A','B','C','D','E','F','G'};
    int weight[][sizeof(data)] = {
        {0,12,0,0,0,16,14},
        {12,0,10,0,0,7,0},
        {0,10,0,3,5,6,0},
        {0,0,3,0,4,0,0},
        {0,0,5,4,0,2,8},
        {16,7,6,0,2,0,9},
        {14,0,0,0,8,9,0}
    };

    Graph graph = CreateGraph(sizeof(data));

    for(i = 0; i < graph->vertexNum; i++)
    {
        graph->vertex[i] = data[i];
    }

    for(i = 0; i < graph->vertexNum; i++)
    {
        for(j = 0; j <= i; j++)
        {
  
            if(weight[i][j] != 0)
            {
                Edge edge = malloc(sizeof(struct ENode));
                edge->v1 = i;
                edge->v2 = j;
                edge->weight = weight[i][j];
                InsertEdge(graph,edge);
            }
        }
    }

    Prim(graph,1);
    printf("\n");

    Kruskal(graph);
    printf("\n");

    return 0;
}

JZTXT

37. 最小生成树

一、什么是最小生成树

二、贪心算法

2.1、Prim算法

2.2、Kruskal算法

2.3、测试程序