首页 > 代码库 > Kruskal

Kruskal

2024-07-03 07:15:24   221人阅读

算法描述：克鲁斯卡尔算法需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系，可以证明其时间复杂度为O（eloge）。

算法过程：

1.将图各边按照权值进行排序

2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。

3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应为n-1条），算法结束。得到的就是此图的最小生成树。

 

克鲁斯卡尔（Kruskal）算法因为只与边相关，则适合求稀疏图的最小生成树。而prime算法因为只与顶点有关，所以适合求稠密图的最小生成树。

#include <iostream>
using namespace std;
const int SIZE = 102;
struct Node
{
    int start;
    int over;
    int len;
};
int father[SIZE];

int Cmp(const void *a, const void *b)
{    return (*(Node *)a).len > (*(Node *)b).len ? 1 : -1;    }

int Find(int n)
{
    while(n != father[n])
        n = father[n];
    return n;
}

int main()
{
    Node arr[5000];
    int n, edge, i, sum, num, fa, fb;
    cout << "请输入节点的数目：";
    cin >> n;
    for(i=1;i<=n;i++)
        father[i] = i;
    edge = n * (n-1) / 2;
    cout << "请输入" << edge << "条路的起点，终点，距离：（假设每两个结点之间都直接连通）\n";
    for(i=0;i<edge;i++)
        cin >> arr[i].start >> arr[i].over >> arr[i].len;
    qsort(arr, edge, sizeof(arr[0]), Cmp);
    sum = 0;
    num = 1;
    for(i=0;i<edge;i++)
    {
        if(num >= n)
            break;
        fa = arr[i].start;
        fb = arr[i].over;
        fa = Find(fa);
        fb = Find(fb);
        if(fa != fb)
        {
            sum += arr[i].len;
            num++;
            if(fa < fb)                      //这里
                father[fb] = fa;
            else
                father[fa] = fb;
        }
    }
    cout << "最小生成树的总长度是: " << sum << endl;
    return 0;
}
View Code

在Kruskal 算法中  把

?
1
2
3
4
if(fa < fb)
father[fb] = fa;
else
father[fa] = fb;

　　换成

father[fa] = fb  也应该没有问题  在  father  数组中起到的是  连通性的作用   通过 递归 找到root ,root相同形成一个环

因此 fa== fb

 

 #include <iostream>
 #include <string.h>
 #include <stdio.h>
 #include <string>
 #include <algorithm>
 const int MAX = 1000;
 using namespace std;
 struct Kruskal
 {
     int a;
     int b;
     int value;
 };
 int v, l;
 int father[MAX];
 bool cmp(const Kruskal& a,const Kruskal&b)
 {
     return a.value < b.value;
 }
 int unionsearch(int x) //查找根结点+路径压缩
{
    return x == father[x] ? x : unionsearch(father[x]);
}

 bool join(int x,int y)
 {
     int root1 = unionsearch(x);
     int root2 = unionsearch(y);
     if(root1 == root2)
     {
         return false;
     }
     else
     {
        father[root1] = root2;
     }
     return true;
 }
 int main()
 {
     int ncase,ltotal,sum;
     bool flag;
     Kruskal edge[MAX];
     scanf("%d",&ncase);
     while(ncase--)
     {
         memset(edge,0,sizeof(edge));
         scanf("%d %d",&v,&l);
         ltotal = 0;sum = 0;flag = false;
         for(int i  =1 ;i<=v;i++)
         {
             father[i] = i;
         }
         for(int i=1;i<=v;i++)
         {
             scanf("%d %d %d",&edge[i].a,&edge[i].b,&edge[i].value);
         }
         sort(edge+1,edge+1+l,cmp);
         for(int i =1 ;i<=l;i++)
         {
             if(join(edge[i].a,edge[i].b))
             {
                 ltotal++;
                 sum+=edge[i].value;
                 cout<<edge[i].a<<"->"<<edge[i].b<<endl;
             }
             if(ltotal==v-1)
             {
                 flag = true;
                 break;
             }
         }
         if(flag)
         {
             printf("%d\n",sum);
         }
         else
            printf("data error. \n");
     }
     return 0;
 }
View Code

 


联系
我们