锐客网

  1. 首页 > it技术 > >

最小生成树-克鲁斯卡尔算法(Kruskal算法)

算法

问题出发点： 对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。
条件控制

1.任意定点之间只有一条通路，不能产生环 2.对于n个顶点的生成树只有n-1条通路即可

具体思路
1.先将边按照边的权值排序 2.从小到大依次判断边,若加入该边不形成环,则将该边加入其中,反之,继续扫描下一条边 3.判断结束条件:加入的边为n-1条

具体实现 【最小生成树-克鲁斯卡尔算法(Kruskal算法)】如何判断是否成环?
//parent[i]表示i结点在已经生成树中可到达结点; int Find(int x){ while(parent[x]>0){ x=parent[x]; } return x; } void Kruskal(){ int k=0,i=0; printf("The lostpath:\n"); while(k

算法实现源码
#include #include #define N 20 #define inex 1001 int c[7][7]={//用邻接表存储图结构，inex表示两端点不可达 {}, {inex,0,6,1,5,inex,inex}, {inex,6,0,5,inex,3,inex}, {inex,1,5,0,5,4,6}, {inex,5,inex,5,inex,inex,2}, {inex,inex,3,6,inex,0,6}, {inex,inex,inex,2,4,6,0}, }; typedef struct edge{ //构造有序图标数据结构 int form; //起始端点 int to; //目标端点 int weight; //两端点边的权值 }E; E sortedge[101],t[101]; //t用于排序，将结果赋值给sortedge int parent[101]={}; //判断是否成环的数据结构 int n=6; //端点数 int em(int k,int i,int j){//因为图为无相图，该函数判断是否该边已经加入变表 for(int z=0; z0&&c[i][j]0){ x=parent[x]; } return x; } void Kruskal(){ int k=0,i=0; printf("The lostpath:\n"); while(k

运行结果 最小生成树-克鲁斯卡尔算法(Kruskal算法)
文章图片

    推荐阅读


    上一篇：leetcode刷题记录|轮转数组——LeetCode198题

    下一篇：flutter学习(1)