数据结构（19）图的最小生成树算法

快来打我* 2023-03-03 13:27 13阅读 0赞

### 数据结构（19）图的最小生成树算法 ###

*   *   *  前言
         *  普里姆（Prim）算法
         *  克鲁斯卡尔（Kruskal）算法
         *  代码
         *   *  GraphMtx.h
             *  GraphMtx.c
             *  Main.c

### 前言 ###

在有n个顶点的图中，要连接所有顶点，只需要n-1条线路。假设每假设一条线路都需要付出一定代价，并且每条线路的代价不一定相同，那么就引出一个新的问题：如何设置线路，使得所有线路的总代价最小呢？

一个连通图的生成树是一个极小的连通子图，它含有图中的全部顶点，但是只有足以构成一棵树的n-1条边；当某棵生成树所拥有的n-1条边的代价总和为最小时，称其为最小生成树。

如何找到这样一棵最小生成树呢？主要有两种算法，即普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。

### 普里姆（Prim）算法 ###

普里姆算法的思想是：从已纳入生成树的顶点集合出发，找到下一个可以到达并且花费代价为最小的顶点，若它不在生成树中，则将其纳入生成树。

显然，算法要求先拥有一个生成树的顶点集合，这意味着在调用算法时，需要指定一个初始的顶点，先把它纳入集合中。  
![img\_1][img_1]

以上图为例，假设初始顶点为A，那么普里姆算法是如何寻找最小生成树的呢？

![img\_2][img_2]

1.  首先，将A顶点纳入顶点集合中，此时可以到达的顶点为B、C、D，其中花费代价最小的顶点为C（A-C），并且C不在顶点集合中，则将C纳入生成树
2.  A、C在顶点集合中，此时可以到达的顶点为B、D、E、F，其中花费代价最小的顶点为F（C-F），并且F不在顶点集合中，则将F纳入生成树
3.  A、C、F在顶点集合中，此时可以到达的顶点为B、D、E，其中花费代价最小的顶点为D（F-D），并且D不在顶点集合中，则将D纳入生成树

![img\_3][img_3]

1.  A、C、D、F在顶点集合中，此时可以到达的顶点为B、E，其中花费代价最小的顶点为B（C-B），并且B不在顶点集合中，则将B纳入生成树
2.  A、B、C、D、F在顶点集合中，此时可以到达的顶点为E，其中花费代价最小的顶点为E（B-E），并且E不在顶点集合中，则将E纳入生成树

这样我们就获得了一个最小生成树，每个顶点之间边的权值总和最小。

那么，如何实现这个算法呢？

可以发现，我们只关心生成树的顶点集合到剩余顶点的**最小花费**。例如，在C顶点加入顶点集合后，顶点集合到B顶点有两条边，即A-B（6）与C-B（5），如果此时需要选择一条连接B顶点，必然会选择C-B；即使以后出现比C-B花费更少的边，也与A-C边无关。

也就是说，我们可以维护一个lowCost数组，它记录了顶点集合到每个顶点的最小花费，如果顶点已经在集合中，则花费为0；如果有未能到达的顶点，则花费为max；否则存放顶点集合中的某个顶点到它的花费（这条线路的花费是最小的）。

那么问题来了：当顶点集合有多个顶点时，我们怎么知道是哪个顶点到目标顶点的花费呢？因此还需要维护一个mst数组，来记录lowCost中的花费，是从哪个顶点出发产生的。

这样，当有新的顶点纳入生成树时，首先将lowCost数组中该顶点的花费置为0，然后从该顶点出发，重新计算到达每个顶点的花费，如果小于已存在的花费，则修改lowCost数组和mst数组的数据。

然后，再遍历新的lowCost数组，找到下一个花费最小的顶点，将其纳入生成树。

![img\_4][img_4]

![img\_5][img_5]

实现普里姆算法的整体思路是：

*  将两个辅助数组创建好
 *  获取到初始顶点的位置，将其纳入生成树中（这个过程相当于初始化两个辅助数组
 *  开始遍历lowCost数组，每次找到最小花费可到达的顶点，将该顶点纳入生成树（重新计算顶点集合到每个顶点的最小花费）
 *  有n个顶点，则需要找到n-1条边，即循环n-1次

//获取两个顶点的距离
    int GetWeight(GraphMtx *g,int v1,int v2){ 
        if (v1 == -1 || v2 == -1) { 
            return DEFAULT_MAX_COST;
        }
        return g->Edge[v1][v2];
    }
    //最小生成树-普里姆算法
    void MinSpanTree_Prim(GraphMtx *g,T vertex){ 
        
        //辅助数组->记录最小的花费
        int *lowCost = (int*)malloc(sizeof(int)*g->NumVertices);
        assert(lowCost != NULL);
        //辅助数组->记录起始顶点
        int *mst = (int *)malloc(sizeof(int)*g->NumVertices);
        assert(mst != NULL);
        
        //获得起始位置
        int k = GetVertexPos(g, vertex);
        //将初始顶点纳入生成树->初始化辅助数组中的数据
        for (int i = 0; i < g->NumVertices; i ++) { 
            if (i != k) { 
                lowCost[i] = GetWeight(g, k, i);
                mst[i] = k;
            }else{ 
                lowCost[i] = 0;
            }
        }
        
        
        int min,minIndex;
        int begin,end;
        int cost;
        for (int i = 0; i < g->NumVertices-1; i ++) { 
            min = DEFAULT_MAX_COST;
            minIndex = -1;
            //找到当前最小花费可到达的顶点
            for (int j = 0; j < g->NumVertices; j ++) { 
                if (lowCost[j] != 0 && lowCost[j] < min) { 
                    //如果它没有存在于顶点集合中->找到了
                    min = lowCost[j];
                    minIndex = j;
                }
            }
            //找到到达该顶点的起始点
            begin = mst[minIndex];
            end = minIndex;
            //输出信息
            printf("%c->%c:%d\n",g->VerticesList[begin],g->VerticesList[end],min);
            
            //将该顶点纳入生成树
            lowCost[minIndex] = 0;
            //重新计算到达每个顶点的最小花费
            for (int j = 0; j < g->NumVertices; j ++) { 
                cost = GetWeight(g, minIndex, j);
                if (cost < lowCost[j]) { 
                    //该顶点的花费比已存的花费少->更新数据
                    lowCost[j] = cost;
                    mst[j] = minIndex;
                }
            }
        }
    }

### 克鲁斯卡尔（Kruskal）算法 ###

如果说，普里姆算法是从顶点出发，去寻找顶点，那么克鲁斯卡尔算法出发则是从边出发来寻找顶点。

其基本思想是：每次寻找当前花费最小的一条边，若该边的两条顶点不在同一个连通子图上，则将其加入到生成树中。

![img\_6][img_6]

如图所示

1.  首先找到当前花费最小的边A-C，A、C顶点不在同一个连通子图上，将其加入生成树中
2.  找到当前花费最小的边D-F，D、F顶点不在同一个连通子图上，将其加入生成树中
3.  找到当前花费最小的边B-E，B、E顶点不在同一个连通子图上，将其加入生成树中

![img\_7][img_7]

1.  找到当前花费最小的边C-F，C、F顶点不在同一个连通子图上，将其加入生成树中
2.  找到当前花费最小的边，此时有三条边代价相等，即B-C、A-D、C-D，选择任意一条边即可。
    
    但是可以发现，此时A、C、D顶点在同一个连通子图上，显然不能连接。因此最终选择B-C边，加入生成树中

这样，同样可以得到一棵最小生成树。

那么，如何判断两个顶点是否在同一个连通子图呢？

我们可以设置一个father数组，用于记录每一个顶点的父结点，假如两个顶点拥有相同的父结点，则说明是在同一个连通子图上。假如顶点的父结点是它本身，说明该顶点就是一个连通子图的根；若不是它本身，则说明它之上还有父结点，则继续向上查找。

![img\_8][img_8]

![img\_9][img_9]

*  当father数组初始化时，每个顶点的父结点都是它本身，说明此时每个顶点都是相互独立的。
 *  将A-C边纳入生成树中，则令C顶点的父结点为A（反之亦可），此时A、C顶点连成一个连通子图，之后的D-F、B-E边同理
 *  将C-F纳入生成树中，先判断C的父结点（A）与F的父结点（F）是否是同一个，不是则可以纳入；令F的父结点的父结点等于C的父结点（反之亦可），这样A-C-F-D连成了一个连通子图
    
    注：假设，F的父结点为D，而D的父结点为它本身，则C-F连接时，是令F的父结点（D）的父结点等于C的父结点（A）。相反地，也可以让C的父结点（A）的父结点等于F的父结点（D）
    
    注注：假设此时，想插入A-D边，则查找A的父结点（A）与D的父结点。虽然father数组中D的父结点为F，但是F的父结点不是它本身，说明其上还有父结点，则继续寻找到F的父结点（A），则A与D拥有同一个父结点，说明是在同一个连通子图中，无法插入
 *  将B-C纳入生成树中，先判断C的父结点（A）与B的父结点（B）是否是同一个，不是则可以纳入；令B的父结点的父结点等于C的父结点（反之亦可），这样A-B-C-D-E-F连成了一个连通子图

可见，克鲁斯卡尔算法有两个主要部分：第一个即判断两个结点的父结点是否是同一个，第二是使一个顶点的父结点的父结点等于另一个顶点的父结点（也就是将两个连通子图连在一起）

int Is_same(int *father,int i,int j){ 
        //找到i的父结点
        while (father[i] != i) { 
            i = father[i];
        }
        //找到j的父结点
        while (father[j] != j) { 
            j = father[j];
        }
        //判断是否一致
        return i == j ? 1 : 0;
    }
    
    void Mark_same(int *father,int i,int j){ 
        //找到i的父结点
        while (father[i] != i) { 
            i = father[i];
        }
        //找到j的父结点
        while (father[j] != j) { 
            j = father[j];
        }
        //使j的父结点的父结点等于i的父结点
        father[j] = i;
    }

克鲁斯卡尔算法是从边出发，而我们选用邻接矩阵作为图的存储方式，并没有存储边的信息。因此在这里我们需要设计一个边的结构，来保存边的两个顶点，和权值。

//边结构
    typedef struct Edge{ 
        //边的起点
        int x;
        //边的终点
        int y;
        //边的权值
        int cost;
    }Edge;

因此，在真正实施克鲁斯卡尔算法时，还需要先将所有边统计出来。同时，由于每次都去寻找代价最小的边，因此可以先根据代价对边进行排序，这样更方便些。

//根据权值对边排序
    int cmp(const void *a,const void *b){ 
        return ((*(Edge *)a).cost - (*(Edge *)b).cost);
    }
    //最小生成树-克鲁斯卡尔算法
    void MinSpanTree_Kruskal(GraphMtx *g){ 
        int n = g->NumVertices;
        Edge *edge = (Edge *)malloc(sizeof(Edge) * (n*(n-1)/2));
        assert(edge != NULL);
        
        //找到所有边
        int k = 0;
        for (int i = 0; i < n; i ++) { 
            for (int j = i; j < n; j ++) { 
                if (g->Edge[i][j] != 0 && g->Edge[i][j] != DEFAULT_MAX_COST) { 
                    edge[k].x = i;
                    edge[k].y = j;
                    edge[k].cost = g->Edge[i][j];
                    k ++;
                }
            }
        }
        
        //将所有边进行排序
        qsort(edge, k, sizeof(Edge),cmp);
        
        //初始化父结点数组
        int *father = (int *)malloc(sizeof(int) * n);
        assert(father != NULL);
        for (int i = 0; i < n; i ++) { 
            father[i] = i;
        }
        
        int v1,v2;
        for (int i = 0; i < n; i ++) { 
            if (!Is_same(father,edge[i].x,edge[i].y)) { 
                //两个顶点不在同一个连通子图上->使其连接
                v1 = edge[i].x;
                v2 = edge[i].y;
                printf("%c->%c : %d\n",g->VerticesList[v1],g->VerticesList[v2],edge[i].cost);
                Mark_same(father,edge[i].x,edge[i].y);
            }
        }
     
    }

### 代码 ###

#### GraphMtx.h ####

#ifndef GraphMtx_h
    #define GraphMtx_h
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    //默认的顶点个数
    #define DEFAULT_VERTEX_SIZE 10
    //初始化的距离
    #define DEFAULT_MAX_COST 0x7FFFFFF
    //顶点的数据类型
    #define T char
    
    //边结构
    typedef struct Edge{ 
        //边的起点
        int x;
        //边的终点
        int y;
        //边的权值
        int cost;
    }Edge;
    
    typedef struct GraphMtx{ 
        //最大的顶点数
        int MaxVertices;
        //现有的顶点数
        int NumVertices;
        //现有的边数
        int NumEdges;
        
        //顶点列表
        T *VerticesList;
        //边->矩阵
        int **Edge;
    }GraphMtx;
    
    //初始化
    void InitGraph(GraphMtx *g);
    
    //展示图
    void ShowGraph(GraphMtx *g);
    
    //获取顶点位置
    int GetVertexPos(GraphMtx *g,T v);
    
    //插入顶点
    void InsertVertex(GraphMtx *g,T v);
    //插入边-无向
    void InsertEdge(GraphMtx *g,T v1,T v2,int cost);
    
    //摧毁图
    void DestoryGraph(GraphMtx *g);
    
    //求v1到v2边的权值
    int GetWeight(GraphMtx *g,int v1,int v2);
    //最小生成树-普利姆算法
    void MinSpanTree_Prim(GraphMtx *g,T vertex);
    //最小生成树-克鲁斯卡尔算法
    void MinSpanTree_Kruskal(GraphMtx *g);
    
    int cmp(const void *a,const void *b);
    void Mark_same(int *father,int i,int j);
    #endif /* GraphMtx_h */

#### GraphMtx.c ####

#include "GraphMtx.h"
    
    //初始化
    void InitGraph(GraphMtx *g){ 
        //数据初始化
        g->MaxVertices = DEFAULT_VERTEX_SIZE;
        g->NumVertices = g->NumEdges = 0;
        
        //开辟储存顶点的空间
        g->VerticesList = (T*)malloc(sizeof(T) * g->MaxVertices);
        assert(g->VerticesList != NULL);
        
        //开辟储存边的空间
        g->Edge = (int **)malloc(sizeof(int*) * g->MaxVertices);
        assert(g->Edge != NULL);
        for (int i = 0; i < g->MaxVertices; i ++) { 
            g->Edge[i] = (int *)malloc(sizeof(int) * g->MaxVertices);
            assert(g->Edge[i] != NULL);
        }
        
        //初始化边
        for (int i = 0; i < g->MaxVertices; i ++) { 
            for (int j = 0; j < g->MaxVertices; j ++) { 
                if (i == j) { 
                    g->Edge[i][j] = 0;
                }else{ 
                    g->Edge[i][j] = DEFAULT_MAX_COST;
                }
            }
        }
    }
    
    //展示图
    void ShowGraph(GraphMtx *g){ 
        
        //打印第一排的顶点
        printf(" ");
        for (int i = 0; i < g->NumVertices; i ++) { 
            printf("%c ",g->VerticesList[i]);
        }
        printf("\n");
        
        //打印边->矩阵
        for (int i = 0; i < g->NumVertices; i ++) { 
            printf("%c ",g->VerticesList[i]);
            for (int j = 0; j < g->NumVertices; j ++) { 
                if (g->Edge[i][j] == DEFAULT_MAX_COST) { 
                    printf("%s ","@");
                }else{ 
                    printf("%d ",g->Edge[i][j]);
                }
            }
            printf("\n");
        }
        printf("\n");
    }
    
    //获取顶点位置
    int GetVertexPos(GraphMtx *g,T v){ 
        for (int i = 0; i < g->NumVertices; i ++) { 
            if (g->VerticesList[i] == v) { 
                return i;
            }
        }
        return -1;
    }
    
    //插入顶点
    void InsertVertex(GraphMtx *g,T v){ 
        if (g->NumVertices == g->MaxVertices) { 
            printf("顶点已满，无法插入\n");
            return;
        }
        g->VerticesList[g->NumVertices ++] = v;
    }
    //插入边
    void InsertEdge(GraphMtx *g,T v1,T v2,int cost){ 
        //获取v1的位置
        int p1 = GetVertexPos(g, v1);
        //获取v2的位置
        int p2 = GetVertexPos(g, v2);
        if (p1 == -1 || p2 == -1) { 
            printf("有顶点不存在\n");
            return;
        }
        
        g->Edge[p1][p2] = g->Edge[p2][p1] = cost;
        g->NumEdges ++;
        
    }
    
    //摧毁图
    void DestoryGraph(GraphMtx *g){ 
        //释放顶点空间
        free(g->VerticesList);
        g->VerticesList = NULL;
        for (int i = 0; i < g->NumVertices; i ++) { 
            free(g->Edge[i]);
        }
        g->Edge = NULL;
        g->MaxVertices = g->NumEdges = g->NumVertices = 0;
    }
    //求v1与v2边的权值
    int GetWeight(GraphMtx *g,int v1,int v2){ 
        if (v1 == -1 || v2 == -1) { 
            return DEFAULT_MAX_COST;
        }
        return g->Edge[v1][v2];
    }
    //最小生成树-普里姆算法
    void MinSpanTree_Prim(GraphMtx *g,T vertex){ 
        
        //辅助数组->记录最小的花费
        int *lowCost = (int*)malloc(sizeof(int)*g->NumVertices);
        assert(lowCost != NULL);
        //辅助数组->记录起始顶点
        int *mst = (int *)malloc(sizeof(int)*g->NumVertices);
        assert(mst != NULL);
        
        //获得起始位置
        int k = GetVertexPos(g, vertex);
        for (int i = 0; i < g->NumVertices; i ++) { 
            if (i != k) { 
                lowCost[i] = GetWeight(g, k, i);
                mst[i] = k;
            }else{ 
                lowCost[i] = 0;
            }
        }
        
        int min,minIndex;
        int begin,end;
        int cost;
        for (int i = 0; i < g->NumVertices-1; i ++) { 
            min = DEFAULT_MAX_COST;
            minIndex = -1;
            for (int j = 0; j < g->NumVertices; j ++) { 
                if (lowCost[j] != 0 && lowCost[j] < min) { 
                    min = lowCost[j];
                    minIndex = j;
                }
            }
            
            begin = mst[minIndex];
            end = minIndex;
            printf("%c->%c:%d\n",g->VerticesList[begin],g->VerticesList[end],min);
            
            lowCost[minIndex] = 0;
            for (int j = 0; j < g->NumVertices; j ++) { 
                cost = GetWeight(g, minIndex, j);
                if (cost < lowCost[j]) { 
                    lowCost[j] = cost;
                    mst[j] = minIndex;
                }
            }
        }
    }
    
    //最小生成树-克鲁斯卡尔算法
    void MinSpanTree_Kruskal(GraphMtx *g){ 
        int n = g->NumVertices;
        Edge *edge = (Edge *)malloc(sizeof(Edge) * (n*(n-1)/2));
        assert(edge != NULL);
        
        //找到所有边
        int k = 0;
        for (int i = 0; i < n; i ++) { 
            for (int j = i; j < n; j ++) { 
                if (g->Edge[i][j] != 0 && g->Edge[i][j] != DEFAULT_MAX_COST) { 
                    edge[k].x = i;
                    edge[k].y = j;
                    edge[k].cost = g->Edge[i][j];
                    k ++;
                }
            }
        }
        
        //将所有边进行排序
        qsort(edge, k, sizeof(Edge),cmp);
        
        //初始化父结点数组
        int *father = (int *)malloc(sizeof(int) * n);
        assert(father != NULL);
        for (int i = 0; i < n; i ++) { 
            father[i] = i;
        }
        
        int v1,v2;
        for (int i = 0; i < n; i ++) { 
            if (!Is_same(father,edge[i].x,edge[i].y)) { 
                //两个顶点不在同一个连通子图上->使其连接
                v1 = edge[i].x;
                v2 = edge[i].y;
                printf("%c->%c:%d\n",g->VerticesList[v1],g->VerticesList[v2],edge[i].cost);
                Mark_same(father,edge[i].x,edge[i].y);
            }
        }
     
    }
    
    int cmp(const void *a,const void *b){ 
        return ((*(Edge *)a).cost - (*(Edge *)b).cost);
    }
    
    int Is_same(int *father,int i,int j){ 
        //找到i的父结点
        while (father[i] != i) { 
            i = father[i];
        }
        //找到j的父结点
        while (father[j] != j) { 
            j = father[j];
        }
        //判断是否一致
        return i == j ? 1 : 0;
    }
    
    void Mark_same(int *father,int i,int j){ 
        //找到i的父结点
        while (father[i] != i) { 
            i = father[i];
        }
        //找到j的父结点
        while (father[j] != j) { 
            j = father[j];
        }
        //使j的父结点的父结点等于i的父结点
        father[j] = i;
    }

#### Main.c ####

#include "GraphMtx.h"
    
    int main(int argc, const char * argv[]) { 
        GraphMtx gm;
        InitGraph(&gm);
        InsertVertex(&gm, 'A');
        InsertVertex(&gm, 'B');
        InsertVertex(&gm, 'C');
        InsertVertex(&gm, 'D');
        InsertVertex(&gm, 'E');
        InsertVertex(&gm, 'F');
    
        InsertEdge(&gm,'A','B',6);
        InsertEdge(&gm,'A','C',1);
        InsertEdge(&gm,'A','D',5);
        InsertEdge(&gm,'B','C',5);
        InsertEdge(&gm,'B','E',3);
        InsertEdge(&gm,'C','D',5);
        InsertEdge(&gm,'C','E',6);
        InsertEdge(&gm,'C','F',4);
        InsertEdge(&gm,'D','F',2);
        InsertEdge(&gm,'E','F',6);
        ShowGraph(&gm);
       
        printf("prim:\n");
        MinSpanTree_Prim(&gm, 'A');
        printf("\n");
        printf("kruskal:\n");
        MinSpanTree_Kruskal(&gm);
    
        DestoryGraph(&gm);
        
        return 0;
    }

[img_1]: /images/20230208/aae7b78c0e924c04a3d033c25e67e781.png
[img_2]: /images/20230208/1aced38ae47c4860b3acff3934607684.png
[img_3]: /images/20230208/c3c6f534693a42d08b507cbee5d3de72.png
[img_4]: /images/20230208/8201e19f843c4c8ab03d9a22e3ff793d.png
[img_5]: /images/20230208/c002c7f7465e4069b4f421a18c5fc0e3.png
[img_6]: /images/20230208/538bdd82b9d8433aa3027a692d0592f5.png
[img_7]: /images/20230208/b769327420a34236b73d7a147e980dd8.png
[img_8]: /images/20230208/8b96a06e5620431db2bde6075c2ac0b4.png
[img_9]: /images/20230208/eae0af763a964e619c6304bed76be821.png