2023年8月1日发(作者：)

C语⾔数据结构与算法---最⼩⽣成树（克鲁斯卡尔算法）⽂章⽬录⼀.克鲁斯卡尔（Kruskal）算法1.算法思想1. 设连通⽹ N = (V,E) ，令最⼩⽣成树初始状态为只有 n 个顶点⽽⽆边的⾮连通图 T=（V,{}），每个顶点⾃成⼀个连通分量2. 在 E 中选取代价最⼩的边，若该边依附的顶点落在 T 中不同的分量上（即：不能成环），则将此边加⼊到 T 中；否则，舍去此边，选取下⼀条代价最⼩的边3. 依次类推，直⾄ T 中所有顶点都在同⼀连通分量上为⽌此时会发现，权值为5的有3条边，但是有两条边不符合（会构成回路）故：2. 克鲁斯卡尔算法的实现边集数组的结构:typedef struct{ int begin; int end; int weight;}Edge将邻接矩阵转化为边集数组：void OperationEdge(Graph G, Edge* edges){ int i, j,k; k = 0; //⽆向图对称，只需转换⼀半即可 for (i = 0; i < ; i++) { for (j = i+1; j < ; j++) { if ([i][j] != INTMAX && [i][j] != 0) { edges[k].begin = i; edges[k].end = j; edges[k].weight = [i][j]; k++; } } } //将weight从⼩到⼤交换排序 Edge tmp; for (i = 0; i < k-1; i++) { for (j = i + 1; j < k; j++) { if (edges[i].weight > edges[j].weight) { tmp = edges[i]; edges[i] = edges[j]; edges[j] = tmp; } } }}克鲁斯卡尔算法：void MinSpanTree_Kruskal(MGraph G){ int i, n, m; Edge edges[MAXSIZE]; //定义边集数组 int parent[MAXSIZE]; //⽤来判断边与边是否会成环 OperationEdge(G, edges); for (i = 0; i < ; i++) { parent[i] = 0; //初始化数组值为 0 } //循环每⼀条边 for (i = 0; i < ; i++) { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) //n!=m,说明没有成环，加⼊⽣成树 { //将此边的结尾顶点放⼊下标为起点的parent中（n是起始顶点，m是结尾顶点） //n---m

这条边符合条件 //表⽰该顶点已经在⽣成树集合中 parent[n] = m; printf("（%d,%d）,weight = %d", edges[i].begin,edges[i].end, edges[i].weight); } }}//查找连线顶点的尾部下标int Find(int *parent，int f){ while(parent[f] > 0) { f = parent[f];

} return f;}对Find函数的理解：整个算法执⾏的过程相当于是将多个树组成⼀个树，Find 函数中的 while 相当于是找到每棵⼩树的根结点，也就是说返回的 n 和 m 的值其实就相当于两棵⼩树的根节点，如果根结点相同，肯定就是同⼀棵树即图连通了；如果不相等，就将两棵⼩树连成⼀棵树即 parent[n] =m。若 while 没有找到根结点，即没有连通，那么这条边就重新建⽴⼀棵⼩树，并以⼀头为根即 f = parent[f]。parent 数组中的 f 位置的值为0，其实也就是找到根结点了对parent数组的理解：parent[n] = m，就是说在 n 的位置上添加数值 m。起初，parent 数组⾥⾯都为 0，进⼊Find函数都是直接返回。parent[0] = 1，相当于下标为 0 的结点的根为1⼆. 普利姆算法与克鲁斯卡尔算法的⽐较1. 时间复杂度普利姆算法： O(n²) （ n为顶点数 ）克鲁斯卡尔算法：O(eloge) （e为边数）2.适应范围普利姆算法：稠密图克鲁斯卡尔算法：稀疏图

2023年8月1日发(作者：)

C语⾔数据结构与算法---最⼩⽣成树（克鲁斯卡尔算法）⽂章⽬录⼀.克鲁斯卡尔（Kruskal）算法1.算法思想1. 设连通⽹ N = (V,E) ，令最⼩⽣成树初始状态为只有 n 个顶点⽽⽆边的⾮连通图 T=（V,{}），每个顶点⾃成⼀个连通分量2. 在 E 中选取代价最⼩的边，若该边依附的顶点落在 T 中不同的分量上（即：不能成环），则将此边加⼊到 T 中；否则，舍去此边，选取下⼀条代价最⼩的边3. 依次类推，直⾄ T 中所有顶点都在同⼀连通分量上为⽌此时会发现，权值为5的有3条边，但是有两条边不符合（会构成回路）故：2. 克鲁斯卡尔算法的实现边集数组的结构:typedef struct{ int begin; int end; int weight;}Edge将邻接矩阵转化为边集数组：void OperationEdge(Graph G, Edge* edges){ int i, j,k; k = 0; //⽆向图对称，只需转换⼀半即可 for (i = 0; i < ; i++) { for (j = i+1; j < ; j++) { if ([i][j] != INTMAX && [i][j] != 0) { edges[k].begin = i; edges[k].end = j; edges[k].weight = [i][j]; k++; } } } //将weight从⼩到⼤交换排序 Edge tmp; for (i = 0; i < k-1; i++) { for (j = i + 1; j < k; j++) { if (edges[i].weight > edges[j].weight) { tmp = edges[i]; edges[i] = edges[j]; edges[j] = tmp; } } }}克鲁斯卡尔算法：void MinSpanTree_Kruskal(MGraph G){ int i, n, m; Edge edges[MAXSIZE]; //定义边集数组 int parent[MAXSIZE]; //⽤来判断边与边是否会成环 OperationEdge(G, edges); for (i = 0; i < ; i++) { parent[i] = 0; //初始化数组值为 0 } //循环每⼀条边 for (i = 0; i < ; i++) { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) //n!=m,说明没有成环，加⼊⽣成树 { //将此边的结尾顶点放⼊下标为起点的parent中（n是起始顶点，m是结尾顶点） //n---m

这条边符合条件 //表⽰该顶点已经在⽣成树集合中 parent[n] = m; printf("（%d,%d）,weight = %d", edges[i].begin,edges[i].end, edges[i].weight); } }}//查找连线顶点的尾部下标int Find(int *parent，int f){ while(parent[f] > 0) { f = parent[f];

} return f;}对Find函数的理解：整个算法执⾏的过程相当于是将多个树组成⼀个树，Find 函数中的 while 相当于是找到每棵⼩树的根结点，也就是说返回的 n 和 m 的值其实就相当于两棵⼩树的根节点，如果根结点相同，肯定就是同⼀棵树即图连通了；如果不相等，就将两棵⼩树连成⼀棵树即 parent[n] =m。若 while 没有找到根结点，即没有连通，那么这条边就重新建⽴⼀棵⼩树，并以⼀头为根即 f = parent[f]。parent 数组中的 f 位置的值为0，其实也就是找到根结点了对parent数组的理解：parent[n] = m，就是说在 n 的位置上添加数值 m。起初，parent 数组⾥⾯都为 0，进⼊Find函数都是直接返回。parent[0] = 1，相当于下标为 0 的结点的根为1⼆. 普利姆算法与克鲁斯卡尔算法的⽐较1. 时间复杂度普利姆算法： O(n²) （ n为顶点数 ）克鲁斯卡尔算法：O(eloge) （e为边数）2.适应范围普利姆算法：稠密图克鲁斯卡尔算法：稀疏图