数据结构应用实例(四)——最小生成树
Content：
- 一、问题描述
- 二、算法思想
- 三、代码实现
- 四、两种算法的比较
- 五、小结
一、问题描述
利用 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);//以邻接表的形式显示图G
int 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和N
for (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("-->");
else
printf("--");
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;
else
return 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;
else
pre[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和pre
p=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].edge
break;//跳出循环
}
//i没有孩子或者E[j].edge <= E[0].edge
E[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
)
O(N^2)
O(N2)；
Kruskal 算法从另一个角度出发，选取边，每次都选取权值最小的、添加之后不构成圈的边进行添加，同样保证了结果为最小生成树，时间复杂度与边的个数 e 有关；为方便后续处理，首先对边按权值大小进行排序，时间复杂度为
O
(
e
l
o
g
2
e
)
O(elog_2e)
O(elog2e)，然后对每条边进行判断并决定是否添加，e 次操作，所以总的时间复杂度为
O
(
e
l
o
g
2
e
)
O(elog_2e)
O(elog2e)；
综合所述，Prim 算法适合顶点相对较少而边相对稠密的网的最小生成树的求解，而 Kruskal 算法适合于求边比较稀疏的网的最小生成树；
五、小结
1、 首先进行一次 BFS，返回遍历到的节点数目，据此判断图是否连通，非连通图不具有最小生成树；
2、 对于 prim 算法，将最小生成树中的节点的 weight[i] 置为0，表示其在最小生成树中；
3、 最小生成树中每增添一个节点，更新其直接后继的 weight 和 pre；
4、 kruskal 算法，为图的结构体添加成员 E ——存放边的结构体数组，成员为两节点编号和边的权值，这样在创建图时，可以直接创建 E，同时，图的数据文件中添加边的条数；
5、 在执行 kruskal 算法时，可对 E 按照边的权值进行堆排序，避免了从邻接矩阵中再次读取边的操作，降低了算法的时间复杂度；
6、 通过 BFS 来实现某一连通分支上所有点的 flag 值的更改；