加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Kruskal算法(克鲁斯克算法)

(2013-08-04 17:19:41)
标签:

kruskal

算法

c

分类: 数据结构

基本思想

假设WN=(V,{E})是一个含有n个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含n个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有n棵树的一个森林。之后,从网的边集E中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有一棵树,也即子图中含有n-1条边为止。

Kruskal算法的时间复杂度由排序算法决定,若采用快排则时间复杂度为O(N log N)。

 

例子:

Kruskal算法(克鲁斯克算法)

 现在用C++具体方法来实现:首先把边的信息储存在记事本kurskal.txt中

 kurskal.txt内容如下:

0 1 34
1 4 12
0 5 19
4 5 26
0 2 46
2 5 25
3 5 25
4 3 38
2 3 17

头文件kurskal.h的定义:

#define maxver 10     //最大顶点数
#define maxedge 100   //最大边数
 
 int parent[maxver];   //父节点
 struct edgegraph      //边集数组
 {
  int from,to;
  int weight;
 };
 edgegraph edge[maxedge];
 int vertexNum,edegeNum;  //顶点数和边数
 int vex1,vex2;    //根节点
 int minweight=0; //最小权重之和

程序kurskal.cpp如下:

#include<iostream>
#include<cstdlib>
#include<fstream>
#include"kruskal.h"


int main()
{
 using namespace std;
    //用来表示顶点数和边数
 cout<<"请输入顶点数和边数:"<<endl;
 cin>>vertexNum;
 cin>>edegeNum;


 //初始化边集数组
 ifstream fin;
 fin.open("kurskal.txt");
 for(int i=0;i<edegeNum;i++)
 {
  fin>>edge[i].from;
  fin>>edge[i].to;
  fin>>edge[i].weight;
 }

 

 //初始化父节点数组;
 for(int j=0;j<edegeNum;j++)
 {
  parent[j]=-1;
 }

 //对函数的声明
 int findroot(int parent[],int v);   //找到根节点
 void kruskal(edgegraph edge[]);      //核心算法,开始查找,输出最小树的分支
 

 //对数组结构体根据weight进行排序
 for (int m=0;m<edegeNum;m++)
 {
  for (int n=0;n<edegeNum-1-m;n++)
  {
   if(edge[n].weight>edge[n+1].weight)
   {
    edge[edegeNum+1]=edge[n+1];
    edge[n+1]=edge[n];
    edge[n]=edge[edegeNum+1];
    
   }
   
  }
 }

 //查看排序的结果
 for(int k=0;k<edegeNum;k++)
 {
  cout<<edge[k].from<<"--"<<edge[k].to<<"--"<<edge[k].weight<<endl;
 }
 kruskal(edge);

 return 0;
}


//findrrot的定义
int findroot(int parent[],int v)

 int t;
 t=v;
 while(parent[t]>-1)
  t=parent[t];
 return t;
}

//krusural的定义
void kruskal(edgegraph edge[])
{
 using namespace std;
 for(int num=0,int i=0;i<edegeNum;i++)
 {
  vex1=findroot(parent,edge[i].from);
  vex2=findroot(parent,edge[i].to);
  if(vex1!=vex2)
  {
   cout<<"("<<edge[i].from<<"--"<<edge[i].to<<"--"<<edge[i].weight<<")"<<endl;
   parent[vex2]=vex1;
   minweight+=edge[i].weight;
   num++;
   if(num==vertexNum-1)
   {
    cout<<"最小权重和为"<<minweight<<endl;
    return;
   }
  }
  
 }
}

运行结果如下:

Kruskal算法(克鲁斯克算法)

 

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有