首页 > 代码库 > Kurskal算法（克鲁斯卡尔算法）
Kurskal算法（克鲁斯卡尔算法）
特点：适用于稀疏图，边比较少的图。如果顶点较少，且为稠密图，则用Prim算法。跟Prim算法的用途相同。时间复杂度为O（e*loge），其中e为边数。
代码：
#include <stdio.h>#include <stdlib.h>#define MAXEDGE 20 //设定边的最大值#define INF 65535 //用来设定边的最大值typedef struct Edge{ int begin; int end; int weight;}Edge; //构建的边结点typedef struct EGraph{ Edge edge[MAXEDGE]; Edge EdgeSorted[MAXEDGE]; int numGraphEdge;}EGraph; //构建的边集数组结构static int Flag[MAXEDGE]; //定义排序时各个顶点是否被比较过的状态，如果被比较过赋给EdgeSorted后，Flag = 1void CreateEGraph(EGraph *G) //构建一个操作的图 int i = 0,j = 0,k = 0,w = 0; printf("请输入图中边的数目：\n"); scanf("%d",&G->numGraphEdge); for(k = 0;k < G->numGraphEdge;k++) { printf("请输入边vi-vj的边的下标 i 和 j ，以及权重w :\n"); scanf("%d,%d,%d",&i,&j,&w); G->edge[k].begin = i; G->edge[k].end = j; G->edge[k].weight = w; } for(k = 0;k < G->numGraphEdge;k++) //初始化标示数组 { Flag[k] = 0; }}void SortEdge(EGraph *G) //对边集数组按权值大小进行排序{ int min,k,i,j; for(i = 0;i < G->numGraphEdge;i++) { min = INF; for(j = 0;j < G->numGraphEdge;j++) { if(Flag[j] == 0 && min >= G->edge[j].weight) { min = G->edge[j].weight; k = j; } } Flag[k] = 1; G->EdgeSorted[i].begin = G->edge[k].begin; G->EdgeSorted[i].end = G->edge[k].end; G->EdgeSorted[i].weight = G->edge[k].weight; } printf("\n*******************************\n"); printf("排序后的权值依次为:\n"); for(i = 0;i < G->numGraphEdge;i++) { printf("%d ",G->EdgeSorted[i].weight); }}int Find(int *parent,int f) //构造parent数组，为了判断最小生成树中是否构成了回路{ while(parent[f] > 0) //注意必须是while循环，直到parent[f]中的值为0，返回parent数组下标f { f = parent[f]; } return f;}//kurskal算法：依次遍历被排好序的边集数组，如果没有构成回路，就把他加入最小生成树，如果构成回路，则无视继续循环void Kruskal(EGraph *G){ int i = 0,m,n; int parent[MAXEDGE]; for(i = 0;i < G->numGraphEdge;i++) { parent[i] = 0; } for(i = 0;i < G->numGraphEdge;i++) { m = Find(parent,G->EdgeSorted[i].begin); n = Find(parent,G->EdgeSorted[i].end); if(m != n) //说明没有形成环路 { parent[m] = n; printf("(%d,%d,%d) ",G->EdgeSorted[i].begin,G->EdgeSorted[i].end,G->EdgeSorted[i].weight); } }}int main(){ EGraph G; //声明一个图 CreateEGraph(&G); //创建图 SortEdge(&G); printf("\n*******************************\n"); printf("\nkurskal得到的最小生成树的边为：\n"); Kruskal(&G); //打印由kurskal算法得到的最小生成树的各个边 printf("\n\n*******************************\n"); return 0;}
Kurskal算法（克鲁斯卡尔算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。