简洁明了的克鲁斯卡尔算法求解

　

克鲁斯卡尔算法

小试牛刀–++克鲁斯卡尔算法++

考研资料书本定义：克鲁斯卡尔算法思想：每次找出侯选边中权值最小的边，就将该边并入生成树中。重复此过程直到所有边都被检测完为止（瞎几把说，不准确，漏了对重复多余边的检测），下面我结合实例来说明。

举例说明：如下图所示，一共有4个节点（1,2,3,4）,相应的一共有C₄²/2=6条边(四个顶点两两对其有12组可能的向量，但由于两组向量本身就是一条边，因此12/2=6)，然后得到的6条边就为（1,3,2,4,5,+&)–其中1条不通的边我们将它看做无穷远+&。

算法描述： 第一步，将六条边进行由小到大排序，排序后就变成了（1,2,3,4,5，+&）。

第二步：选出最左长度为1的一条边出来（即最小的一条边），将边对应的两个结点1,2做某种标志（后面会介绍）

第三步：从剩下来的边（2,3,4,5，+&）中选出最左边的一条边2出来，看一下相应的两个端点2，4是否有同一种标志，如果有两种标志，就把该两点对应的标志合成一种标志，并且输出该边对应的长度

以此类推，直到把所有的边都遍历完，即结束

如果不理解，看下面我的实际样例[一个求路径最短的算法例子]

/提示一下，标志位的作用光看是不行的，要结合自己对实例的理解，笔者已经尽力写的详细了/

存储边和相应两端结点的结构体

typedef struct node{
       int l,r;     /*指的是一条边两端的端点值*/
       int w;       /*指的是这条边对应的边长权值*/
}node;
typedef struct mp{
    node a[maxsize];/*存储每条边的信息*/
}mp;

接下来就可以执行这算法了

目标，输出能连通该图的最短路径长度（使用克鲁斯卡尔算法）；

初始条件：已经存入n条边长的两端顶点值和边长权值bas[i],(0<=i

int in(int a) //将同一类的结点归为一个公共标志位
{
    while(a!=visit[a])//仔细理解这段代码，照着这段代码遍历下去指向了一个源点标志为
    {
        a=visit[a];
    }
        return a;
}
void lest(mp a,int v)//a是一个矩阵，包含了图的结点数(a.n)和边数(a.d)
{
    int i,a,b,sum=0:
    int visit[max];//用来存储各个结点的标志
    for(i=0;i<a.n;i++)
    {
        visit[i]=i;//给每个节点定好各自的标志
    }
    sort(bas);//排序函数，对图里的边进行从小到大排序
    for(i=0;i<a.d;i++)
    {
        a=in(bas.a);
        b=in(bas.b);
        if(a!=b)
        {
            visit[a]=b;
            sum+=bas.w;//将符合条件的边长累计相加，得到总长。
        }
    }
}

由于是博主第一次写博客，对一些操作还不熟练，写的不好请见谅，以后我会晚上定期更新博客内容，嗯晚安.

相关阅读

最小生成树之克鲁斯卡尔算法和普里姆算法

一、最小生成树简介   假设有一个很实际的问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个