kruskal算法

kruskal算法

        【算法定义】

假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按Kruskal算法构造最小生成树的过程为:先构造一个只含 n 个顶

点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,从网的

边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的

两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类

推,直至森林中只有一棵树,也即子图中含有 n-1条边为止,可见题:

【海岛帝国系列赛】No.4 海岛帝国:LYF的太空运输站

上面有转自百科的分析,是一道最小生成树算法的题。一个有N条边的连通图,如果让它不连通,那么它要有N-1条边。

算法过程:

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

2.将图遍历一次,找出权值最小的边,排序就可以实现,查找可以用并查集实现,(条件:此次找出的边不能和已加入最小生成树集合的边构成环),若符合条件,则加入最小生成树的集合中。不符合条件则继续遍历图,寻找下一个最小权值的边。

那么,排序有没有快的树上搜索呢?

当然有,我们可以每当插入一个节点,和它的左儿子右儿子比较,如果大,就把此节点向下一层移动,而对应的后代向上移动,然后遍历整个树。

来看看这一道题吧:神奇的排序

总体来说就是排序,虽然时间限制宽的桶排序也能过QAQ

但我们今天讲的是树,

来看看具体的代码吧,用了个堆排序:

#include<iostream>
using namespace std;
int h[81];
int n;
void swap(int x,int y)//交换节点权值
{
   int t;
   t=h[x];
   h[x]=h[y];
   h[y]=t;
   return ;
}
void siftdown(int i)//编号i的节点向下移动
{
     int t,flag=0;
     while(i*2<=n&&flag==0)
     {
         if(h[i]<h[i*2]) t=i*2;
         else t=i;
         if(i*2+1<=n)
             if(h[t]<h[i*2+1])
                 t=i*2+1;
         if(t!=i)
         {
             swap(t,i);
             i=t;
         }
         else flag=1;
     }
     return ;
}
void creat()//建堆
{
     int i;
     for(i=n/2;i>=1;i--) siftdown(i);
     return ;
 }
void heapsort()//对堆排序
{
     while(n>1)
     {
         swap(1,n);
         n--;
         siftdown(1);
     }
     return ;
}
int main()
{
    int i,num;
    scanf("%d",&num);
    for(i=1;i<=num;i++) scanf("%d",&h[i]);
    n=num;
    creat();//一定要先建造堆
    heapsort();
    printf("%d",h[1]);
    for(i=2;i<=num;i++) printf(" %d",h[i]);
}

  

下面,我们来看一看LYF的太空站那一题的树上排序。

树上排序如果数据小时间跟桶排序等排序差不多,甚至可能比归并和快排慢一些,但是却很实用,树上排序用它还是不错的。

【实例代码】

#include<iostream>
using namespace std;
int dis[20],book[20]={0};
int h[20],pos[20],size;
void swap(int x,int y)
{
     int t;
     t=h[x];
     h[x]=h[y];
     h[y]=t;
     t=pos[h[x]];
     pos[h[x]]=pos[h[y]];
     pos[h[y]]=t;
     return ;
}
void siftdown(int i)//节点向下转换
{
     int t,flag=0;
     while(i*2<=size&&flag==0)
     {
          if(dis[h[i]]>dis[h[i*2]]) t=i*2;
          else t=i;
          if(i*2+1<=size)
              if(dis[h[t]]>dis[h[i*2+1]]) t=i*2+1;
          if(t!=i)
          {
              swap(t,i);
              i=t;
          }
          else flag=1;
     }
     return ;
}
void siftup(int i)//节点向上转换
{
     int flag=0;
     if(i==1) return ;
     while(i!=1&&flag==0)
     {
         if(dis[h[i]]<dis[h[i/2]]) swap(i,i/2);
         else flag=1;
         i/=2;
     }
     return ;
}
int pop()//弹出
{
    int t;
    t=h[1];
    pos[t]=0;
    h[1]=h[size];
    pos[h[1]]=1;
    size--;
    siftdown(1);
    return t;
}

  

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

转载的Kruskal算法代码:

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define N 150
using namespace std;
int m,n,u[N],v[N],w[N],p[N],r[N];
int cmp(const int i,const int j) {return w[i]<w[j];}
int find(int x) {return p[x]==x?x:p[x]=find(p[x]);}
int kruskal()
{
    int cou=0,x,y,i,ans=0;
    for(i=0;i<n;i++) p[i]=i;
    for(i=0;i<m;i++) r[i]=i;
    sort(r,r+m,cmp);
    for(i=0;i<m;i++)
    {
        int e=r[i];x=find(u[e]);y=find(v[e]);
        if(x!=y) {ans += w[e];p[x]=y;cou++;}
    }
    if(cou<n-1) ans=0;
    return ans;
}

int main()
{
    int i,ans;
    while(scanf("%d%d",&m,&n)!=EOF&&m)
    {
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&u[i],&v[i],&w[i]);
        }
        ans=kruskal();
        if(ans) printf("%d\n",ans);
        else printf("?\n",ans);
    }
    return 0;
}

 算法图解:

时间: 06-20

kruskal算法的相关文章

HDU 1389 继续畅通工程【最小生成树,Prime算法+Kruskal算法】

继续畅通工程 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 21871    Accepted Submission(s): 9356 Problem Description 省政府"畅通工程"的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可).现得到城镇道路统计表,表中列

hdu 1875 畅通工程再续(kruskal算法计算最小生成树)

畅通工程再续 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 18411    Accepted Submission(s): 5769 Problem Description 相信大家都听说一个"百岛湖"的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的小岛时都要通过划小船来实现.现在政府决定大力发展百岛湖,发展首先

ZOJ1372 POJ 1287 Networking 网络设计 Kruskal算法

题目链接:ZOJ1372 POJ 1287 Networking 网络设计 Networking Time Limit: 2 Seconds      Memory Limit: 65536 KB You are assigned to design network connections between certain points in a wide area. You are given a set of points in the area, and a set of possible

ZOJ 1718 POJ 2031 Building a Space Station 修建空间站 最小生成树 Kruskal算法

题目链接:ZOJ 1718 POJ 2031 Building a Space Station 修建空间站 Building a Space Station Time Limit: 2 Seconds      Memory Limit: 65536 KB You are a member of the space station engineering team, and are assigned a task in the construction process of the statio

POJ 2421 Constructing Roads 修建道路 最小生成树 Kruskal算法

题目链接:POJ 2421 Constructing Roads 修建道路 Constructing Roads Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 19698   Accepted: 8221 Description There are N villages, which are numbered from 1 to N, and you should build some roads such that e

最小生成树之Kruskal算法

上一篇文章中提到了最小生成树的Prim算法,这一节继续探讨一下最小生成树的Kruskal算法.什么是最小生成树算法上文已经交代过了,所以我们直接从Kruskal的步骤开始介绍. 1.Kruskal算法的步骤: a.假定拓扑图的边的集合是E,初始化最小生成树边集合G={}. b. 遍历集合E中的所有元素,并且按照权值的大小进行排序. c. 找出E中权值最小的边e . d .如果边e不和最小生成树集合G中的边构成环路,则将边e加到边集合G中:否则测试下一条权值次小的边,直到满足条件为止. e. 重复

Prim算法和Kruskal算法求最小生成树

Prim算法 连通分量是指图的一个子图,子图中任意两个顶点之间都是可达的.最小生成树是连通图的一个连通分量,且所有边的权值和最小. 最小生成树中,一个顶点最多与两个顶点邻接:若连通图有n个顶点,则最小生成树中一定有n-1条边. Prim算法需要两个线性表来进行辅助: visited: 标记已经加入生成树的顶点:(它的功能可以由tree取代) 初始状态:生成树根节点为真,其它为0. tree: 记录生成树,tree[x]保存顶点x的直接根节点下标,若x为树的根节点则tree[x]为其自身. 初始状

kruskal算法求最小生成树(jungle roads的kruskal解法)

注意: 注意数组越界问题(提交出现runtimeError代表数组越界) 刚开始提交的时候,边集中边的数目和点集中点的数目用的同一个宏定义,但是宏定义是按照点的最大数定义的,所以提交的时候出现了数组越界问题,以后需要注意啦. Description The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads betwe

POJ 1797 kruskal 算法

题目链接:http://poj.org/problem?id=1797 开始题意理解错.不说题意了. 并不想做这个题,主要是想测试kruskal 模板和花式并查集的正确性. 已AC: /* 最小生成树 kruskal算法 过程:每次选取没有参与构造最小生成树并且加入之后不会构成回路的边中权值最小的一条 作为最小生成树的一条新边.直至选择了V-1条边. */ #include <stdio.h> #include <string.h> #include <iostream>

最小生成树2(Kruskal算法)

Kruskal算法: 1:按照边的权值的顺序从小到大查看一遍,如果不产生圈(重边也算),就把当前这条边加入到生成树中,基本算法证明和prim一样 2:如何判断是否产生负圈,假设现在要把连接顶点u和顶点v的边e加入到生成树中,如果加入之前u和v不在同一个联通分量里,那么加入e也不会产生负圈,反之,如果u和v在同一个连通分量里,那么一定会产生圈,可以使用并查集高效的判断是否属于同一个连通分量 PS:Kruskal算法耗时在于其对边的排序,算法复杂度为O(|E|log|V|) struct node