数据结构,最小生成树克鲁斯卡尔算法的实现

小程序710 更新时间：2025-06-08 23:55:53

2023年8月1日发(作者：)

摘要

设计了一个用C/C++编写程序实现克鲁斯卡尔最小生成树算法，该程序操作简单，界面清晰，易于为用户所接受。

关键词：克鲁斯卡尔，邻接矩阵，最小生成树，vc++。目录

1 课题描述 ....................................................................................................................................... 1

2 问题分析和任务定义 ................................................................................................................... 2

3 逻辑设计 ....................................................................................................................................... 3

4 详细设计 ....................................................................................................................................... 4

5 程序编码 ..................................................................................................................................... 11

6 程序调试与测试 ......................................................................................................................... 17

7 结果分析 ..................................................................................................................................... 19

8 总结............................................................................................................................................. 20

参考文献 ......................................................................................................................................... 21 1课题描述

用C/C++编写程序实现克鲁斯卡尔最小生成树算法。假设要在n个城市之间建立通讯联络网，则连通n个城市只需要n-1条线路。这是我们设计一个最小生成树的程序用来算出最节省经费的前提下建立这个通信站。1 2问题分析和任务定义

假设连通网N=（V,{E}）,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直到T中所有顶点都在同一连通分量上为止。

2 3逻辑设计

设计思想：采用邻接矩阵来存储图，然后采用克鲁斯卡尔算法求出最小生成树。

结构体定义

函数模块一

（图的创建）

采用邻接矩阵做存储结构

函数模块二

（求最小生成树）

克鲁斯卡尔算法

主函数引用函数模块一、二，实现算法设计

1）．定义结构体。

2）．采用邻接矩阵做存储结构创建图（函数模块一）。

3）．采用克鲁斯卡尔算法求出该图的最小生成树（函数模块二）。

4）．在主函数里面分别调用以上各个函数，最终实现设计目的。

3 4详细设计

4.1．程序结构

·函数CreateMGraph

用来实现图的创建，以及图的相关信息的存储。图的存储采用邻接矩阵存储结构。

·函数minitree_KRUSKAL

用来求图的最小生成树。图的最小生成树有普利姆算法和克鲁斯卡尔算法可以实现，本段代码使用的是克鲁斯卡尔算法，这也是本题所要求使用的。

·各个函数间的联系

先调用函数CreateMGraph实现图的创建，然后调用函数minitree_KRUSKAL求出该图的最小生成树

4.2．设计说明

·在开始的时候添加一些限制条件方便函数的功能实现例如：

#define MaxVertexNum 100 //最大顶点个数

#define QueueSize 30

#define M 30

·模块一：图的创建

·结构体定义为：

typedef struct

{

VertexType vexs[MaxVertexNum]; //顶点表

Link edges[MaxVertexNum][MaxVertexNum]; //图中当前的相连接的两个顶点

int n,e; //图中当前的顶点数和边数

}MGraph;

·函数定义为：

MGraph CreateMGraph()

{

4 MGraph G;

int i,j,k,ch3;

char ch1,ch2;

printf("请输入该图的顶点数和边数:n");

scanf("%d,%d",&(G.n),&(G.e));

printf("请输入该图的顶点信息:n");

for(i=1;i<=G.n;i++)

{

getchar();

scanf("%c",&([i]));

}

for(i=1;i<=G.n;i++)

for(j=1;j<=G.n;j++)

[i][j].w=0;

printf("请输入该图每条边对应的两个顶点的名称:n");

for(k=1;k<=G.e;k++)

{

scanf("%c",&ch1);

printf("请输入第%d条边的顶点序号：",k);

scanf("%c %c",&ch1,&ch2);

printf("请输入第%d条边的权值大小：",k);

scanf("%d",&ch3);

for(i=1;ch1!=[i];i++);

for(j=1;ch2!=[j];j++);

e[p].vexh=i;

e[p].vext=j;

e[p].weight=[i][j].w=ch3; //权值

e[p].flag=0;

p++;

}

return G;

}

5 流程如图4.1所示

创建图使用的是函数MGraph CreateMGraph()，该图的存储结构是邻接矩阵，先对图的结构体进行定义，再进行初始化。在函数中需要手动输入图的参数（如顶点数、边数、顶点信息、相连接的顶点、边的权值等）用来建立图并且确定图的邻接矩阵。最后在完成图的信息输入即建立图以后输出图的邻接矩阵表。

·模块二：求图的最小生成树。

void minitree_KRUSKAL(MGraph *G)

{

int i,min,j,k;

VEX t[M];

for(i=1;i<=G->n;i++)

{

t[i].data=G->vexs[i];

t[i].jihe=i;

}

i=1;

while (in)

{

min=MaxVertexNum;

for (j=0;je;j++)

{

if (e[j].weight

{

min=e[j].weight;

6 k=j;

}

if (t[e[k].vexh].jihe!=t[e[k].vext].jihe)

{

e[k].flag=1;

for (j=1;j<=G->n;j++)

if (t[j].jihe==t[e[k].vext].jihe)

t[j].jihe=t[e[k].vexh].jihe;

t[e[k].vext].jihe=t[e[k].vexh].jihe;

i++;

} else e[k].flag=2;

}

printf("克鲁斯卡尔最小生成树：n");

for (i=0;ie;i++)

if (e[i].flag==1)

printf("(%d,%d) %dn",e[i].vexh,e[i].vext,e[i].weight);//输出最小生成树

}

该步骤应用的是克鲁斯卡尔算法，它的基本思想是：每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入MST（Minimum Spanning Tree最小生成树），并将所在的2个连通分量合并，直到只剩一个连通分量。

7 流程如图4.2所示。

8 开始请输入该图的顶点数和边数G.e>(G.n-1)*G.n/2输入错误,请重新输入请输入该图的顶点信息i=1i<=++getchar();scanf("%c",&([i]))i=1i++i<==1j<=++

[i][j].w=0请输入该图每条边对应的两个顶点的名称K=1k<=G.e请输入第%d条边的顶点序号请输入第%d条边的权值K++大小i=1ch1!=[i]j=1i++ch2!=[j]return Gj++e[p].vexh=i;e[p].vext=j;

e[p].weight=[i][j].w=ch3; //权值

e[p].flag=0;p++;结束图4.1

9

开始i=1i++i<=G->nt[i].data=G->vexs[i];t[i].jihe=i;i=1inmin=MaxVertexNum;j=0j++jee[j].weight

k=j;t[e[k].vexh].jihe!=t[e[k].vext].jiheNe[k].flag=2e[k].flag=1j=1j++j<=G->nt[j].jihe==t[e[k].vext].jihet[j].jihe=t[e[k].vexh].jihe;

t[e[k].vext].jihe=t[e[k].vexh].jihe;

i++;i=0i++iee[i].flag==1输出最小生成树结束图4.210

5 程序编码

#include

#define MaxVertexNum 100 //最大顶点个数

#define M 30

typedef enum{FALSE,TRUE}Boolean;

Boolean visited[MaxVertexNum]; //访问标志数组

typedef char VertexType;

typedef int EdgeType;

typedef struct Lnode

{

int w;//相应一条边的权值

}Link;

typedef struct

{

VertexType vexs[MaxVertexNum]; //顶点表

Link edges[MaxVertexNum][MaxVertexNum]; //图中当前的相连接的两个顶点

int n,e; //图中当前的顶点数和边数

}MGraph;

typedef struct

{

char data;

11 int jihe;

}VEX;

typedef struct

{

int vexh,vext; //边顶点

int weight; //权值

int flag; //标记

}EDGE;

EDGE e[M];

int p=0;

/*************************图邻接矩**************************/

MGraph CreateMGraph()

{

MGraph G;

int i,j,k,ch3;

char ch1,ch2;

printf("请输入该图的顶点数和边数:n");

scanf("%d,%d",&(G.n),&(G.e));

while(G.e>(G.n-1)*G.n/2)

{

printf("输入错误,请重新输入:n");

12

阵的建立 scanf("%d,%d",&(G.n),&(G.e));

}

printf("请输入该图的顶点信息:n");

for(i=1;i<=G.n;i++)

{

getchar();

scanf("%c",&([i]));

}

for(i=1;i<=G.n;i++)

for(j=1;j<=G.n;j++)

[i][j].w=0;

printf("请输入该图每条边对应的两个顶点的名称:n");

for(k=1;k<=G.e;k++)

{

scanf("%c",&ch1);

printf("请输入第%d条边的顶点序号：",k);

scanf("%c %c",&ch1,&ch2);

printf("请输入第%d条边的权值大小：",k);

scanf("%d",&ch3);

for(i=1;ch1!=[i];i++);

for(j=1;ch2!=[j];j++);

e[p].vexh=i;

13 e[p].vext=j;

e[p].weight=[i][j].w=ch3; //权值

e[p].flag=0;

p++;

}

return G;

}

/*************************克鲁斯卡尔*************************/

void minitree_KRUSKAL(MGraph *G)

{

int i,min,j,k;

VEX t[M];

for(i=1;i<=G->n;i++)

{

t[i].data=G->vexs[i];

t[i].jihe=i;

}

i=1;

while (in)

{

min=MaxVertexNum;

14

最小生成树 for (j=0;je;j++)

{

if (e[j].weight

{

min=e[j].weight;

k=j;

}

if (t[e[k].vexh].jihe!=t[e[k].vext].jihe)

{

e[k].flag=1;

for (j=1;j<=G->n;j++)

if (t[j].jihe==t[e[k].vext].jihe)

t[j].jihe=t[e[k].vexh].jihe;

t[e[k].vext].jihe=t[e[k].vexh].jihe;

i++;

}

else e[k].flag=2;

}

printf("克鲁斯卡尔最小生成树：n");

for (i=0;ie;i++)

if (e[i].flag==1)

15

printf("(%d,%d) %dn",e[i].vexh,e[i].vext,e[i].weight);//输出最小生成树

}

/****************************主函数调用**********************************/

int main()

{

MGraph G;

printf("n");

printf("**********************************************************n");

printf("*** 克鲁斯卡尔算法求图的最小生成树

***n");

printf("**********************************************************n");

G=CreateMGraph(); //建立该图的邻接矩阵

minitree_KRUSKAL(&G); //克鲁斯卡尔算法最小生成树

return 0;

}

16 6 程序调试与测试

运行程序后如图所示

图6.1

输入错误数组后如图所示

图6.2

17 继续输入正确数组后如图所示

图6.3

18 7 结果分析

程序运行时如果输入的点大于边减一再乘以边除以2，那就是说输入的数组是错误的，此时程序提醒输入错误，在重新输入。如果输入正确那么程序会输出最小生成树。

19 8 总结

这个程序运用函数CreateMGraph来实现图的创建，以及图的相关信息的存储。图的存储采用邻接矩阵存储结构。在运用函数minitree_KRUSKAL来求图的最小生成树。图的最小生成树有普利姆算法和克鲁斯卡尔算法可以实现，本段代码使用的是克鲁斯卡尔算法，这也是本题所要求使用的。在整个程序中先调用函数CreateMGraph实现图的创建，然后调用函数minitree_KRUSKAL求出该图的最小生成树。

这个程序实现了最小生成树的生成。在整个程序的设计过程中有太多的错误以及不懂的地方，虽然在最后完成了程序设计，但是我发现了我的更多的不足，在以后的学习中我会更加努力。

20 参考文献

[1] 严蔚敏，吴伟民.数据结构(C语言版)[M].北京：清华大学出版社,2002

[2] 李春葆.数据结构(C语言版)习题与解析[M]. 北京：清华大学出版社,2002

[3] 钱能.C++程序设计教程[M]. 北京：清华大学出版社,2003

21