【图的最小生成树】之kruskal

目录

前言

一、什么是最小生成树

二、greedy algorithm贪婪算法和kruskal克鲁斯卡尔

1.greedy algorithm贪婪算法

2.kruskal克鲁斯卡尔

3. 代码实现

前言

无论是什么程序都要和数据打交道，一个好的程序员会选择更优的数据结构来更好的解决问题，因此数据结构的重要性不言而喻。数据结构的学习本质上是让我们能见到很多前辈在解决一些要求时间和空间的难点问题上设计出的一系列解决方法，我们可以在今后借鉴这些方法，也可以根据这些方法在遇到具体的新问题时提出自己的解决方法。（所以各种定义等字眼就不用过度深究啦，每个人的表达方式不一样而已），在此以下的所有代码都是仅供参考，并不是唯一的答案，只要逻辑上能行的通，写出来的代码能达到相同的结果，并且在复杂度上差不多，就行了。

一、什么是最小生成树

什么是生成树？什么又是最小生成树？对于一个连通图而言生成树是一个极小连通子图，之前我们说过，一个连通图的生成树可以有多个，如下图所示的连通图，就可以有三个生成树；

我们可以从上图中得出结论：

①对于一个包含n个顶点的完全图有n个生成树；②而对于有n个顶点的连通图而言，生成树有n-1条边；

继续观察上图，深入思考生成树中顶点和边的关系，我们还可以得到：

③一个连通图的生成树包含相同的顶点数和边数；④生成树不存在环！；⑤生成树的基础上删除任意一条边都会导致图的不连通，而如果添加任意一条边都会形成环；

了解了生成树的概念和属性之后，回到我们的问题：什么是最小生成树？最小生成树是针对带权图来说的边的权值（权值之和）最小的生成树就是最小生成树。

二、greedy algorithm贪婪算法和kruskal克鲁斯卡尔

1.greedy algorithm贪婪算法

tips：本文使用英文的原因是中文的翻译是有多种的，而每个人接触到的中文翻译可能不一样这就可能导致不知道我在说什么；希望未来这些专有名词是我们发明的，这样就是那些老外来学中文了^_^

在讲Kruskal之前我们要先讲讲什么是greedy algorithm贪婪（心）算法；

贪婪的思想：每一步都作出当下最优解，通过局部最优解来实现整体最优；

而对于一个具体问题要确定它是否有贪婪性质，需要去证明每一个贪婪选择能不能导致整体最优；当一个问题的最优解包含子问题的最优解的时候，也满足贪婪思想，叫最优子结构性质；

2.kruskal克鲁斯卡尔

Kruskal其实就是包含了贪婪的思想的一种算法；对于如下这么一个带权图：

Kruskal就是将每一个顶点都看作一个单独的树（也就是把这个图看做一个森林），不断地去找与之相邻的权值最小的点，同时不能成环，最后得到的生成树就是一个最小生成树。如下图所示：

3. 代码实现

那么理清了Kruskal的逻辑之后，就是代码要怎样实现；在上文的描述中，很明显我们更侧重的对象是边，因为我们是要找权值最小的边，那么是不是用边集数组的结构来存储边的信息，最能实现这个操作。（这里边集数组是用来找权值最小的边，而不是用来构成图的，至于选择哪种图的存储结构来构成图，这里我用最简单的邻接矩阵实现，实际上都一样）

而边集数组的构成很简单：一个元素begin用来存储一条边的开始节点的信息，end用来存储一条边的结束节点的信息，最后一个元素weight记录这条边的权值；

//边集数组typedef struct {int begin;int end;int weihgt;}Edges;

记住我们是要找权值最小的边，那么我们可以直接让边集数组中的边按照权值从小到大排序，这样就可以直观的得到权值小的边了

void sort(Edges e[], AdjMatrix* G){int i, j;for(i = 0; i < G->numE; i++){for(j = 0; j < G->numE; j++){if(e[i].weihgt > e[j].weihgt){Swapn(e, i, j);}}}printf("按权排序后的为：\n");for(i = 0; i < G->numE; i++){printf("(%d %d)%d\n", e[i].begin, e[i].end, e[i].weihgt);}}

我把上述的步骤具现化成如下表格；表格最左边一栏表示顶点的信息（为了方便描述，这里我直接让顶点的下标和顶点的值一样，实际上应该通过输入的值在顶点数组中返回对应的下标）右边三栏就是边集数组；

那么问题来了，要怎么判断成不成环？这里可以回顾之前在树中的并查集，是不是可以通过并查集中元素相不相交的问题，也就是某一个顶点在最小生成树中的终点和另一个顶点的终点是否相同来，判断有没有成环

#define MAXVEX 200int parent[MAXVEX];//并查集数组

从边集数组的第一个边开始：开始节点V4、结束节点V7，第二个边V2、V8判断有没成环，没有成环就把它们拿出来；

对于剩下的元素同理，当我们遍历到第八个边的时候,发现V5和V6成环了，如果成环了那么就跳过，剩下的边操作一样...

而根据生成树的属性：对于n个顶点的连通图而言生成树有n-1条边，那么满足这个条件了就停止，最后得到的最小生成树如下图所示

我把并查集数组也具象化成如下表格；

设定初始化为0 表示指向自己，回顾刚才连边的过程，如果没有成环，就找开始节点的最终的结束节点，把结束节点的下标存入开始节点；（什么是最终结束的节点？以V1为例，V1的结束节点是：V1->V5->V8->V6，即最终结束的节点是V6）

从边集数组中第一个边开始，开始节点V4，结束节点是V7，所以在并查集数组中V4下标的那一格存入V7的下标

同理第二条边，开始节点V2结束节点V8，所以并查集数组中下标为2的元素的值是V8的下标8；

如果有成环，又如边集数组（1,2,8）中：V1的终点指向V6，V2 的终点也指向V6，成环所以跳过。最终的并查集数组如下所示

至此，所有的工作都完成了，结束。

全部代码

#include<stdio.h>#include<stdlib.h>#define MAXVEX 200#define INFINTIY 65535//克鲁斯卡尔 贪婪算法//邻接矩阵typedef struct AdjacentMatrix{//顶点集int Vertices[MAXVEX];//边集int Arc[MAXVEX][MAXVEX];//顶点数 边数int numV, numE;}AdjMatrix;//用带权无向邻接矩阵生成图//边集数组typedef struct {int begin;int end;int weihgt;}Edges;int Find(int* parent, int f){while(parent[f] > 0){f = parent[f];}return f;}void sort(Edges e[], AdjMatrix* G){int i, j;for(i = 0; i < G->numE; i++){for(j = 0; j < G->numE; j++){if(e[i].weihgt > e[j].weihgt){//交换函数，暂时没学后面会讲Swapn(e, i, j);}}}printf("按权排序后的为：\n");for(i = 0; i < G->numE; i++){printf("(%d %d)%d\n", e[i].begin, e[i].end, e[i].weihgt);}}void Kruskal(AdjMatrix* G){Edges e[20];//边集数组//判断两边之间是否存在环 并查集int parent[MAXVEX];int k = 0;//根据图的存储来构建边集数组for(int i = 0; i < G->numV; i++){for(int j = 0; j < G->numV; j++){//带权图邻接矩阵小于最大值 说明有边if(G->Arc[i][j] < INFINTIY){e[k].begin = i;//开始节点e[k].end = j;//结束节点e[k].weihgt = G->Arc[i][j];k++;}}}//针对边集数组排序(按照权值排序)sort(e, G);//由于算法没学 这里构建图的时候按权值排序构建//初始化辅助数组for(int i = 0; i < G->numV; i++){parent[i] = 0;}//构建最小生成树for(int i = 0; i < G->numE; i++)//循环遍历每一条边 直到放进了所有的边{//并查集 查//在边集数组中 查找每一条边的起点 和 终点int n = Find(parent, e[i].begin);int m = Find(parent, e[i].end);//n m没有构成环 或m n指向自己if(n != m || n == m == 0){//把这个节点的尾节点的下标放入parent中parent[n] = m;printf("(%d,%d)--%d这两点属于最小生成树的一部分", e[i].begin, e[i].end, e[i].weihgt);}}}