kruskal适合稀疏图
定义边结构体
typedef struct { int begin; int end; int weight; }Edge;
算法实现代码
//邻接矩阵转边集数组 void MGraph2EdgeArr(MGraph G, Edge* edge); //找到顶点index的根节点下标返回 int Find(int* parent, int index); //使用克鲁斯卡尔算法进行最小生成树的创建 void MiniSpanTree_Kruskal(MGraph G); //邻接矩阵转编辑数组,按照权值排序,由小到大 void MGraph2EdgeArr(MGraph G, Edge* edge) { int i, j,k=0; Edge temp; int min; for (i = 0; i < G.numVertexes;i++) { for (j = i + 1; j < G.numVertexes;j++) { if (G.arc[i][j]!=INFINITY) //有边 { edge[k].begin = i; edge[k].end = j; edge[k].weight = G.arc[i][j]; k++; } } } //按照冒泡大小进行排序 for (i = 0; i < k;i++) { for (j = i; j < k;j++) { if (edge[j].weight<edge[i].weight) { temp = edge[i]; edge[i] = edge[j]; edge[j] = temp; } } } } int Find(int* parent, int f) { while (parent[f] > 0) f = parent[f]; return f; } void MiniSpanTree_Kruskal(MGraph G) { Edge edges[MAXVEX]; //定义边集数组 int parent[MAXVEX]; //定义生成树的父节点,也可以使用结构体,但是更加浪费空间 int i,n,m; MGraph2EdgeArr(G, edges); //邻接矩阵转边集数组 //开始进行初始化 for (i = 0; i < MAXVEX; i++) parent[i] = 0; //这里是0代表根节点,我们也可以使用-1,正负无穷等 //进行合并操作 for (i = 0; i < G.numEdges;i++) { n = Find(parent, edges[i].begin); //找到顶点edges[i].begin的根节点下标 m = Find(parent, edges[i].end); //找到顶点edges[i].end的根节点位置 if (n!=m) //若是根节点下标不是一样的,就说不在一棵树上,不会形成环,我们放心合并 { parent[n] = m; //将n树合并到m树,表示该边被放入生成树 } } }