在图论中,树是指无回路存在的连通图。一个连通图的生成树是指包含了所有顶点的树。如果把生成树的边的权值总和作为生成树的权,那么权值最小的生成树就称为最小生成树。因为最小生成树在实际中有很多应用,所以我们有必要了解怎样生成最小生成树。构造最小生成树的两种常用方法:Kruskal算法、Prim算法。本文介绍Kruskal算法,Prim算法在下篇文章中介绍。
Kruskal算法是从另一条途径来求网络的的最小生成树。设G=(V, E)是一个有n个顶点的连通图,则令最小生成树的初值状态为只有n个顶点而无任何边的非连通图T=(V, {空集}),此时图中每个顶点自成一个连通分量。按照权值递增的顺序依次选择E中的边,若该边依附于T中两个不同的连通分量,则将此边加入TE中,否则舍去此边而选择下一条代价最小的边,直到T中所有顶点都在同一连通分量上为止。这时的T,便是G的一棵最小生成树。
物理老师曾说过,图像比文字的信息量大得多,这可以从一幅图像和一篇文章所占电脑的存储空间大小明显得出。因此我们可以同下面的图解过程了解Kruskal算法的思想:
在该算法中,每次都要寻找最短边,如果用邻接矩阵实现的话,则需要对整个矩阵扫描一遍,时间复杂度较高,如果采用邻接表的话,由于每条边都被连接两次,使得寻找时间加倍。所以采用如下结构体:
#include<stdio.h> #define M 8 //边数 #define N 6 //顶点数 //图的存储结构体 typedef struct { int startvex,endvex;//边的两个顶点 int length;//边长 int sign;//是否被选择,1表示被选择,0表示未被选择,2表示选择后形成环,被抛弃 }edge; edge T[M]; int flag1[N];//标记顶点是否已被选中 void Kruskal(edge T[M],int *flag1) { int i,j,k,l,min; int a[M]={0,0,0,1,1,1,2,3,3,4};//边的两个顶点及边的长度 int b[M]={1,4,5,2,3,5,3,4,5,5}; int c[M]={10,19,21,5,6,11,6,18,14,33}; //int a[M]={0,0,0,1,1,2,3,4};//边的两个顶点及边的长度 //int b[M]={1,3,5,2,4,3,4,5}; //int c[M]={7,3,5,6,9,8,4,2}; for(i=0;i<N;i++) flag1[i]=i; for(i=0;i<M;i++)//初始化 { T[i].startvex=a[i]; T[i].endvex=b[i]; T[i].length=c[i]; T[i].sign=0; } j=0; int flag=0;//记录最小边的序号 while(j<N-1) { flag=0; min=10000; for(i=0;i<M;i++) { if(T[i].sign==0) { if(T[i].length<min) { k=T[i].startvex; l=T[i].endvex; flag=i; min=T[i].length; } } } T[flag].sign=1;//标记被选中 //printf("k=%d,l=%d: ",k,l); //printf("\n"); if(flag1[k]==flag1[l])//当边的两个顶点都已经被选择,说明若选择该边就会形成环 { T[flag].sign=2;//表示抛弃该边 //printf("ok "); } else { j++; for(i=0;i<N;i++) if(flag1[i]==l) flag1[i]=flag1[k]; } //for(int ii=0;ii<M;ii++) // printf(" %d ",T[ii].sign); //printf("\n\n"); } } void main() { Kruskal(T,flag1); for(int i=0;i<M;i++) printf("%d ",T[i].sign); printf("\n"); }
程序的结果与上面的图解的结果稍有不同,但是正确的,因为最小生成树有时候是不唯一的。
注:如果程序出错,可能是使用的开发平台版本不同,请点击如下链接: 解释说明
原文:http://blog.csdn.net/tengweitw/article/details/17380353
作者:nineheadedbird