数据结构应用实例(四)——最小生成树

一、问题描述

  利用 prim 算法和 kruskal 算法实现最小生成树问题；

二、算法思想

  首先判断图是否连通，只有在连通的情况下才进行最小树的生成；

三、代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxx 999999
#pragma warning(disable:4996)typedef struct arc//弧
{	int index;//指向节点编号float weight;//边的权值struct arc *next;
}AR;typedef struct edge
{int i,j;//边的起点和终点编号float edge;//边的权值
}EG;typedef struct MyGraph
{int type;//0表示无向图，1表示有向图int arcnum,vexnum;//边的个数、顶点个数char **vexname;//存放顶点名称的二维数组	AR *N;//表头数组float **A;//邻接矩阵，这里使用float型EG *E;//存放边的三元组
}GH;int findvex(char *s,GH *G);//找到图G中名称为s的节点编号，并将其返回
void creatGraph(GH *G);//创建图G
void showGraph(GH *G);//以邻接表的形式显示图Gint isconnect(GH *G);//判断图G是否连通，是则返回1，否则返回0
int BFSvisit(int start,GH *G);//对图G从start号点开始广度优先遍历，返回访问过的节点个数void prim(GH *G,int start);//利用prim算法，求图G中以start为起点的最小生成树
void showTree(AR *N,char **vexname,int n);//显示最小生成树，N表示表头数组，vexname中存放顶点名称，n表示节点数量void kruskal(GH *G);//利用kruskal算法，求图G中的最小生成树
void heapsort(EG *E, int n);//对含有n条边的三元组E进行堆排序
void adjust(int index, EG *E, int n);//对利用顺序表E表示的含有n个节点的完全二叉树的index号节点进行筛选
void changeflag(int m,int y,int *flag, AR *N,int n);//将图G中m号节点所在的连通分支上的点的flag统一赋值为y，N为表头数组，n表示原图中节点个数int main(void)
{GH *G;int begin;//起点编号//创建图G=(GH *)malloc(sizeof(GH));creatGraph(G);printf("图的邻接表形式:\n");showGraph(G);//if (!isconnect(G))//{//	printf("该图不连通，不具有最小生成树.\n");
//		exit(-1);
//	}printf("该图连通，寻找最小生成树:\n");printf("\n\n====================prim算法========================\n");printf("请输入起点编号(-1结束):");scanf("%d", &begin);while (begin != -1){prim(G, begin);printf("请输入起点编号(-1结束):");scanf("%d", &begin);}printf("\n\n================kruskal算法========================\n");kruskal(G);free(G);return 0;
}int findvex(char *s,GH *G)//找到图G中名称为s的节点编号，并将其返回
{for(int i=0;i<G->vexnum;i++){if(strcmp(s,G->vexname[i])==0)return i;}printf("该点不存在\n");exit(-1);
}void creatGraph(GH *G)//创建图G
{int i,j,k,n,m;float edge;char filename[]="graph.txt";char str[10],str1[10];FILE *fp;AR *p;fp=fopen(filename,"r");if(!fp){printf("文件打开失败!\n");exit(-1);}//读取图的类型和节点数量fscanf(fp,"%d%d",&G->type,&n);	G->vexnum=n;//分配空间G->vexname=(char **)malloc(n*sizeof(char *));G->N=(AR *)malloc(n*sizeof(AR));G->A=(float **)malloc(n*sizeof(float *));//初始化A和Nfor (i = 0; i < n; i++){G->N[i].next = NULL;G->A[i] = (float *)malloc(n*sizeof(float));for (j = 0; j < n; j++)G->A[i][j]=maxx;}//读取顶点名称for(i=0;i<n;i++){fscanf(fp,"%s",str);//先分配空间G->vexname[i]=(char *)malloc(strlen(str)*sizeof(char));strcpy(G->vexname[i],str);}    //读取边fscanf(fp,"%d",&m);G->arcnum=m;//边的个数G->E=(EG *)malloc((m+1)*sizeof(EG));//0号位置不存放数据for(k=1;k<=m;k++){fscanf(fp,"%s%s%f",str,str1,&edge);i=findvex(str,G);j=findvex(str1,G);//邻接表中添加节点p=(AR *)malloc(sizeof(AR));p->index=j;p->weight=edge;p->next=G->N[i].next;G->N[i].next=p;//邻接矩阵G->A[i][j]=edge;//三元组G->E[k].i=i;G->E[k].j=j;G->E[k].edge=edge;if(G->type==0){//邻接表中添加节点p=(AR *)malloc(sizeof(AR));p->index=i;p->weight=edge;p->next=G->N[j].next;G->N[j].next=p;//邻接矩阵G->A[j][i]=edge;}}fclose(fp);
}void showGraph(GH *G)//以邻接表的形式显示图G
{int i;AR *p; //用于遍历for (i = 0; i < G->vexnum; i++){printf("%s",G->vexname[i]);p=G->N[i].next;while (p){if (G->type == 1)printf("-->");elseprintf("--");printf("%s(%.2f)",G->vexname[p->index],p->weight);p=p->next;}printf("\n");}printf("\n");
}int isconnect(GH *G)//判断图G是否连通，是则返回1，否则返回0
{int k;k=BFSvisit(0,G);//k：广度优先遍历访问到的节点个数if(k==G->vexnum)return 1;elsereturn 0;
}int BFSvisit(int start,GH *G)//对图G从start号点开始广度优先遍历，返回访问过的节点个数
{int i,n;int *visit;int *q;int front,rear;AR *p;//空间分配n=G->vexnum;visit=(int *)malloc(n*sizeof(int));q=(int *)malloc(n*sizeof(int));//初始化for(i=0;i<n;i++)visit[i]=0;	visit[start]=1;q[0]=start;front=0;rear=1;while(front!=rear){p=G->N[q[front]].next;//对出队点的直接后继进行遍历//printf("%s\n",G->vexname[q[front]]);	front++;while (p){if (visit[p->index] == 0)//如果未被访问，添加访问标记，入队{visit[p->index]=1;q[rear]=p->index;rear++;}p=p->next;}		}free(visit);free(q);return rear;//返回广度优先遍历访问到的节点个数
}void prim(GH *G, int start)//利用prim算法，求图G中以start为起点的最小生成树
{int i,n;int *pre;float *weight;	AR *N,*p;float min;int next;n=G->vexnum;pre=(int *)malloc(n*sizeof(int));//前驱数组weight=(float *)malloc(n*sizeof(float));//距生成树的最短距离，值为0.0表示属于生成树N=(AR *)malloc(n*sizeof(AR));//表头数组，用于存放最小生成树	//1.初始化for (i = 0; i < n; i++){if (G->A[start][i] < maxx)pre[i] = start;			elsepre[i] = -1;weight[i] = G->A[start][i];N[i].next=NULL;}weight[start]=0;//起点放到生成树中//2.寻找距离已生成树最近的顶点min=maxx;for (i = 0; i < n; i++){if (weight[i] != 0 && weight[i] < min)//从与原图中与最小生成树连通的节点中选择{min=weight[i];next=i;}}while (min < maxx){weight[next]=0;//3.放入最小生成树中//相应地添加节点p=(AR *)malloc(sizeof(AR));p->index=next;p->weight=G->A[pre[next]][next];p->next=N[pre[next]].next;N[pre[next]].next=p;if (G->type == 0){p=(AR *)malloc(sizeof(AR));p->index=pre[next];p->weight=G->A[pre[next]][next];p->next=N[next].next;N[next].next=p;}//4.更新weight和prep=G->N[next].next;while (p){if (weight[p->index] != 0 && weight[p->index] > p->weight){weight[p->index]=p->weight;pre[p->index]=next;}p=p->next;}//继续寻找min=maxx;for (i = 0; i < n; i++){if (weight[i] != 0 && weight[i] < min){min=weight[i];next=i;}}}//结果显示showTree(N,G->vexname,n);free(pre);free(weight);free(N);
}void showTree(AR *N, char **vexname, int n)//显示最小生成树，N表示表头数组，vexname中存放顶点名称，n表示节点数量
{int i;AR *p;printf("最小生成树的邻接表形式如下:\n");for (i = 0; i < n; i++){	p=N[i].next;if (p){printf("%s", vexname[i]);while (p){printf("--%s(%.2f)", vexname[p->index], p->weight);p = p->next;}printf("\n");}}printf("\n");
}void kruskal(GH *G)//利用kruskal算法，求图G中的最小生成树
{int i;int m,n;int p,q;int *flag;	AR *N,*t;m=G->arcnum;n=G->vexnum;flag=(int *)malloc(n*sizeof(int *));//位于同一连通分量的节点的flag值相同N=(AR *)malloc(n*sizeof(AR));//表头数组，用于存放最小生成树//1.初始化for (i = 0; i < n; i++){flag[i] = i;//各自为营N[i].next = NULL;}//2.对存放边的三元组G->E进行堆排序heapsort(G->E,m);//3.挑取边for (i = 1; i <= m; i++){   //读取两端节点编号p=G->E[i].i;q=G->E[i].j;if(flag[p]!=flag[q])//4.若两端位于不同的连通分支，表示该边可选{changeflag(q,flag[p],flag,N,n);//将q号节点所在的连通分支上的点的flag改为flag[p]//相应地添加节点t=(AR *)malloc(sizeof(AR));t->index=q;t->weight=G->A[p][q];t->next=N[p].next;N[p].next=t;//无向图需要双边添加节点if (G->type == 0){t = (AR *)malloc(sizeof(AR));t->index=p;t->weight=G->A[p][q];t->next=N[q].next;N[q].next=t;}}}//结果显示showTree(N,G->vexname,n);free(flag);free(N);
}void heapsort(EG *E, int n)//对含有n条边的三元组E进行堆排序
{int i;//首先调整所有的父节点for (i = n / 2; i >= 1; i--)adjust(i,E,n);//然后进行n-1趟堆排序，找出n-1个最大值for (i = 1; i <= n - 1; i++){   //首先进行首尾交换E[0]=E[1];E[1]=E[n-i+1];E[n-i+1]=E[0];//然后进行调整adjust(1,E,n-i);}
}void adjust(int index, EG *E, int n)//对利用顺序表E表示的含有n个节点的完全二叉树的index号节点进行筛选
{int i,j;i=index;j=2*i;E[0]=E[i];//哨兵while (j <= n){if (j + 1 <= n)//保证j始终指向较大的孩子{if(E[j+1].edge>E[j].edge)j=j+1;}if (E[j].edge > E[0].edge)//如果大于哨兵{E[i]=E[j];//将值赋给父节点i=j;//更新循环变量j=2*i;}else//E[j].edge <= E[0].edgebreak;//跳出循环}//i没有孩子或者E[j].edge <= E[0].edgeE[i]=E[0];
}void changeflag(int m,int y,int *flag, AR *N,int n)//将图G中m号节点所在的连通分支上的点的flag统一赋值为y，N为表头数组，n表示原图中节点个数
{   //利用BFS，访问m号节点所在的连通分支，更改其flag值int *q;int front,rear;AR *p;q=(int *)malloc(n*sizeof(int));//初始化flag[m]=y;q[0]=m;front=0;rear=1;while (front != rear){p=N[q[front]].next;front++;while (p){if (flag[p->index] != y){flag[p->index]=y;q[rear]=p->index;rear++;}p=p->next;}}free(q);
}

四、两种算法的比较

  两种算法从不同的角度提出了最小生成树的构造方法：
  Prim 算法从选节点的角度出发，每次都选距离生成树最近的节点，从而保证了最后的结果为最小生成树，时间复杂度与顶点个数 N 有关；每次选择最近顶点，需要进行一次遍历，比较 N 次，之后将其添加进最小生成树，更新 weight 和 pre，一次遍历，N 次操作，总共需要选择 N-1 次，所以 prim 算法的时间复杂度为 $O(N^2)$；
  Kruskal 算法从另一个角度出发，选取边，每次都选取权值最小的、添加之后不构成圈的边进行添加，同样保证了结果为最小生成树，时间复杂度与边的个数 e 有关；为方便后续处理，首先对边按权值大小进行排序，时间复杂度为$O(elo{g}_{2}e)$，然后对每条边进行判断并决定是否添加，e 次操作，所以总的时间复杂度为 $O(elo{g}_{2}e)$；
  综合所述，Prim 算法适合顶点相对较少而边相对稠密的网的最小生成树的求解，而 Kruskal 算法适合于求边比较稀疏的网的最小生成树；

五、小结

1、 首先进行一次 BFS，返回遍历到的节点数目，据此判断图是否连通，非连通图不具有最小生成树；
2、 对于 prim 算法，将最小生成树中的节点的 weight[i] 置为0，表示其在最小生成树中；
3、 最小生成树中每增添一个节点，更新其直接后继的 weight 和 pre；
4、 kruskal 算法，为图的结构体添加成员 E ——存放边的结构体数组，成员为两节点编号和边的权值，这样在创建图时，可以直接创建 E，同时，图的数据文件中添加边的条数；
5、 在执行 kruskal 算法时，可对 E 按照边的权值进行堆排序，避免了从邻接矩阵中再次读取边的操作，降低了算法的时间复杂度；
6、 通过 BFS 来实现某一连通分支上所有点的 flag 值的更改；