系列文章目录
1. 最小生成树三种方法的代码实现
2.最小生成树-动画设计
目录
系列文章目录
前言
一、算法介绍
算法（1）
算法（2）
算法
5、Prim和Kruskal算法比较说明
二、代码讲解
1. 库引入
2. 随机生成矩阵
3. 文件的输出
三、整体代码展示
总结
前言
数据结构最小生成数当中普利姆算法和克鲁斯卡尔算法再加一种普利姆算法的改进，对每一种算法进行了详细的介绍，并比较了三个算法的区别。
因为如果要生成最小生成树的时候，需要知道顶点和边的数据，这就需要不断的调用数据，而如果需要改变顶点数，就需要改文件，比较麻烦，故，此程序采用随机生成矩阵的方式生成最小生成树。
本程序若单单只有表面算法，会呈现出工作量较小的感觉，为了让此次课设有眼前一亮的感觉，所以引用了这一库，可以用图的方式呈现出无向网以及不同算法的最小生成树，具体代码在第二篇文章/m0_53533553/article/details/119538716中详细介绍。
一、算法介绍
算法（1）
I. 建立一个辅助数组closedge[],先对其进行初始化，让closedge[i]中的vexadj存储第一个出发点的字符(假设为A),lowcost存储邻接矩阵中第一个出发点所在的行的各元素值（出发点到其他各点的权值）。如表1.
| Closedeg[i] |
1 |
2 |
3 |
4 |
5 |
6 |
| vexadj |
A |
A |
A |
A |
A |
|
| lowcost |
0 |
28 |
∞ |
26 |
49 |
∞ |
表1
II. 寻找closedge[]的lowcost中不为0且权值最小的下标k=4，并输出closedge[4]中存的字符到4对应的顶点的字符(A-D)，用代码表示为：closedge[k].vexadj—[k].
III. 将选过的点的lowcost标记为0。
IV. 再比较邻接矩阵中第k行各点的值与closedeg[i]中lowcost所存储的值，选择权值较小的存储到lowcost当中，并把顶点字符存储到vexadj当中。如表2
| Closedeg[i] |
1 |
2 |
3 |
4 |
5 |
6 |
| vexadj |
A |
A |
A |
A |
D |
|
| lowcost |
0 |
28 |
∞ |
0 |
49 |
91 |
表2
V. 以此类推，重复II、III、IV步骤，直到循环n-1次，则表示n各顶点、n-1条边全部遍历完成，最小生成树创建完成。
算法（2）
I. 将方法1中的辅助结构体换成两个辅助数组start[]和mark[],start[]存储到i点的距离最小的字符的下标，mark[i]标记是否遍历过，遍历过标记为1。假设第一个出发点为A,先初始化start[i]=1,mark[1]=1,其余为0，如表3所示。
| i |
1 |
2 |
3 |
4 |
5 |
6 |
| Start[i] |
1 |
1 |
1 |
1 |
1 |
1 |
| Mark[i] |
1 |
0 |
0 |
0 |
0 |
0 |
| [start[i]][i].adj |
∞ |
28 |
∞ |
26 |
49 |
∞ |
表3
II. 寻找mark[i]!=1且[start[i]][i].adj当中最小的权值的下标k=4，并输出start[4]所对应的顶点字符到4所对应的顶点字符（A-D），用代码表示：[start[k]]-[k].
III. 将选过的点mark[i]标记为1.
IV. 比较邻接矩阵中第k行各点的值是否比strat[i]行各点的值小，如果小，将strat[i]的值换成k。如表4所示。
| i |
1 |
2 |
3 |
4 |
5 |
6 |
| Start[i] |
1 |
1 |
1 |
1 |
1 |
4 |
| Mark[i] |
1 |
0 |
0 |
1 |
0 |
0 |
| [start[i]][i].adj |
∞ |
28 |
∞ |
26 |
49 |
91 |
表4
具体代码如下：
for(j=1;j<=;j++){
if(mark[j]!=1){
if([k][j].adj<[start[j]][j].adj)
start[j]=k;
}
}
V. 重复II、III、IV的步骤，直到所有的mark[i]的值全为1，表示所有的顶点遍历完成，最小生成树建立完成。
算法
I. 创建辅助结构体数组KEdge h[MAXNUM]以及整形数组fat[]。h[i].a存储第i条最小边的第一个顶点，h[i].b存储第i条最小边的第二个顶点，h[i].w存储第i条边的权值，fat[i]存储与第i个顶点相连的前一顶点（找到这个顶点的树的头结点，防止闭环）。同时设置has变量判断是否所有的顶点都遍历完成。
II. 初始化两个数组，将fat[i]初始化为i,如表6所示。h[i]初始化邻接矩阵中上三角不为无穷的元素的顶点位置和权值。如表6所示。
具体代码如下：
for(i=1;i<=;i++){
for(j=i+1;j<=;j++){
if([i][j].adj<=100){
h[k].a=i; //行
h[k].b=j; //列
h[k].w=[i][j].adj;
k++;
}
}
}
| i |
1 |
2 |
3 |
4 |
5 |
6 |
| Fat[i] |
1 |
2 |
3 |
4 |
5 |
6 |
表5
| a |
b |
w |
|
| H[1] |
1 |
2 |
28 |
| H[2] |
1 |
4 |
26 |
| H[3] |
1 |
5 |
49 |
| H[4] |
2 |
6 |
9 |
| H[5] |
3 |
5 |
42 |
| H[6] |
2 |
6 |
96 |
| H[7] |
5 |
6 |
81 |
表6
III. 对h[i]中的w进行升序排序，采用了简单选择排序的方法。
IV. 当has不等于顶点数减一时，利用root函数寻找h[i].a（此时为2）和h[i].b（此时为6）的根结点，根节点寻找思想：当前一节点就是他本身时，则说明是根节点。具体代码如下：
int Root(int x,int fat[]){
if(fat[x]!=x) return Root(fat[x],fat);
else return x;
}
分别赋给x、y，当x!=y时，令fat[y]=x,并输出[h[i].a]-[h[i].b].此时x=1,y=6,x!=y,令fat[6]=1,并输出A-F.此时fat[i]个数如表7所示。
| i |
1 |
2 |
3 |
4 |
5 |
6 |
| Fat[i] |
1 |
2 |
3 |
4 |
5 |
1 |
表7
V. 重复IV的步骤，直到has==顶点个数减一时结束，最小生成树建立完成。
5、Prim和Kruskal算法比较说明
- 辅助数组不同。第一种prim算法定义了一个Closedeg[i]的结构体数组，其中vexadj是到i所对应的顶点字符的最短的顶点的字符，最短路径是lowcost，判断最小边时是比较lowcost中存的数据选择，如果新的结点比现存的权值小，就进行交换。第二种prim算法定义了Start[i]数组，存储的是到i所对应顶点的最短的顶点所对应的数字，相当于第一种prim算法里的vexadj,判断最小边时是比较邻接矩阵里第start[i]行和新加入的第K行各列元素的大小，如果比现存的权值小，就进行交换。Kruskal算法定义了一个h[i]的结构体数组，存入各边的顶点以及权值，进行升序排序后寻找权值最小的边。用fat[i]数组判断是否构成闭环。
- 结束循环方式不同。第一种prim算法当循环次数大于顶点数-1时退出。第二种prim算法定义了mark[i]数组，当所有的值都变为1时退出。Kruskal算法定义了has变量，当变量数等于顶点数-1时退出。
- 输出方式不同。如表8所示。
| Prim1 |
closedge[k].[k] |
| Prim2 |
[start[k]]-[k] |
| kruskal |
[h[i].a]-[h[i].b] |
表8
二、代码讲解
1. 库引入
#include<>
#include<>
#include<>
#include<>
#include<>
#include<>
#include<>2. 随机生成矩阵
- 先对上三角的元素随机生成{x|x>0&&x<=150}的数, 利用以下的代码表示：G->arcs[i][j].adj=rand()%151。
- 再对角线元素赋值无穷，大于100的元素也令其等于无穷，这样就构成了上三角的邻接矩阵。
- 又因为是无向网，所以利用：G->arcs[j][i]=G->arcs[i][j]代码进行对称填充，构成了完整的邻接矩阵。
/*随机生成图*/
void RandomNumbers(MGraph *G){
int i,j;
srand((unsigned)time(NULL));
for(i=1;i<=G->vexnum;i++){
//对角线为无穷
G->arcs[i][i].adj=INFINITY;
for(j=i+1;j<=G->vexnum;j++){
G->arcs[i][j].adj=rand()%151; //随机生成0-150
G->arcs[j][i]=G->arcs[i][j]; //对称填充
}
}
//对大于100的赋予无穷
for(i=1;i<=G->vexnum;i++){
for(j=i+1;j<=G->vexnum;j++){
if(G->arcs[i][j].adj==0||G->arcs[i][j].adj>100)
G->arcs[i][j].adj=INFINITY;
}
}
}3. 文件的输出
该文件为了第二个程序可以画出无向网
输出格式如下：
第一行书写顶点个数
第二行两个为一组，分别书写每个顶点的横纵坐标
第三行三个为一组，分别书写线段从第几个顶点到第几个顶点，以及两顶点之间的权值
该文件为了第二个程序可以用普利姆算法画出最小生成树
该文件为了第二个程序可以用克鲁斯卡尔算法画出最小生成树
输出格式如下：
两个为一组，分别书写从第几个顶点到第几个顶点
三、整体代码展示
#include<>
#include<>
#include<>
#include<>
#include<>
#include<>
#include<>
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define INFINITY 99999 //无穷,足够大
#define MAX 20 //最大顶点数
#define MAXNUM 1000
#define Gra 30
typedef int Status;
typedef int VRType; //顶点关系类型
typedef char VertexType; //顶点类型
typedef struct{
VRType adj; //权值即城市间的距离
}ArcCell,AdjMatrix[MAX+1][MAX+1];
/*无向网*/
typedef struct{
VertexType vexs[MAX+1]; //顶点向量 顶点字符
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //网的当前顶点数和弧数
}MGraph;
/*辅助数组*/
typedef struct{
VertexType vexadj; //较早加入边的端点
VRType lowcost; //当前边的权值
}Edge;
typedef struct{
int a,b; //端点
int w; //权值
}KEdge;
/*图形化坐标存储*/
typedef struct{
int x; //横坐标
int y; //纵坐标
}Graphics[Gra+1];
void RandomNumbers(MGraph *G);//随机生成图
void GreateUDN_M(MGraph *G);//对结构体赋值
int Locate_vexM(MGraph G,VertexType u);//定位顶点u的位置
void printUDN_M(MGraph G);//输出距离网的邻接矩阵
void MinTree_Prim(FILE *fp1,MGraph G,VertexType u);//使用prim算法从顶点u出发构建最小生成树T，并输出T的各条边
int Minimum(Edge closedge[],int n); //求出T的下个结点，第k结点||返回最小边的端点
void MinTree_Prim2(MGraph G,VertexType u);//使用prim算法从顶点u出发构建最小生成树T，并输出T的各条边
int Minimum2(MGraph G,int start[],int mark[]);//求出T的下个结点，第k结点||返回最小边的端点
void MinTree_Kruskal(FILE *fp2,MGraph G);//kruskal算法构建最小生成树T，并输出T的各条边
void Sort(KEdge a[],int n);//使用选择排序按权值排序
int Root(int x,int fat[]);//寻找x的根结点
void Unionn(int x,int y,int fat[]);//加入集合，并查集的一部分
int Seek(char c);
/*随机生成图*/
void RandomNumbers(MGraph *G){
int i,j;
srand((unsigned)time(NULL));
for(i=1;i<=G->vexnum;i++){
//对角线为无穷
G->arcs[i][i].adj=INFINITY;
for(j=i+1;j<=G->vexnum;j++){
G->arcs[i][j].adj=rand()%151; //随机生成0-150
G->arcs[j][i]=G->arcs[i][j]; //对称填充
}
}
//对大于100的赋予无穷
for(i=1;i<=G->vexnum;i++){
for(j=i+1;j<=G->vexnum;j++){
if(G->arcs[i][j].adj==0||G->arcs[i][j].adj>100)
G->arcs[i][j].adj=INFINITY;
}
}
}
/*对结构体的具体值赋值*/
void GreateUDN_M(MGraph *G){
int i,j,k=65;
//给矩阵赋值
printf("输入你要构建通信网络城市的个数（不大于30）：");;
scanf("%d",&G->vexnum);
//对节点附等字母
for(i=1;i<=G->vexnum;i++){
G->vexs[i]=(char)k; //ASCII码值强制转换
k++;
}
//随机生成图
RandomNumbers(G);
G->arcnum=0;
//计入权值小于100且不等于0的
for(i=0;i<=G->vexnum;i++){
for(j=i+1;j<=G->vexnum;j++){
if(G->arcs[i][j].adj<=100&&G->arcs[i][j].adj!=0){
G->arcnum++;
}
}
}
printf("\n随机城市构建完成！！\n\n");
}
/*定位顶点u的位置*/
int Locate_vexM(MGraph G,VertexType u){
int i;
for(i=1;i<=;i++){
if([i]==u)
return i; //返回u字符在G中的下标
}
return 0;
}
/*显示邻接矩阵*/
void printUDN_M(MGraph G){
int i,j,k=65;
printf("\n\t**距离网的邻接矩阵如下:\n\n\t ");
for(i=1;i<=;i++){
printf("%-4c",k);
[i]=(char)k;
k++;
}
printf("\n\t");
k=65;
for(i=1;i<=;i++){
printf("%-4c",k);
for(j=1;j<=;j++){
if([i][j].adj==0||[i][j].adj>100){
printf("∞ ");
}
else{
printf("%-4d",[i][j].adj);
}
}
printf("\n\t");
k++;
}
}
/*使用prim算法从顶点u出发构建最小生成树T，并输出T的各条边*/
void MinTree_Prim(FILE *fp1,MGraph G,VertexType u){
int i,j,k,s;
fp1=fopen("C:\\Users\\86151\\Desktop\\help\\","w");
Edge closedge[MAX+1]; //0号单元弃用 /*closedge[i]中的vexadj存储顶点中到[i]字符的*/
/*最短路径的字符lowcost存储路径距离*/
int minprice=0; //距离
k=Locate_vexM(G,u); //把顶点u的下标赋给K
//辅助数组初始化
for(j=1;j<=;j++){
if(j!=k){
closedge[j].vexadj=u;
closedge[j].lowcost=[k][j].adj;
}
}
closedge[k].lowcost=0;
printf("使用prim算法得到的最小生成树的各边及其权值为:\n\n");
printf(" 城市 权值\n");
for(i=1;i<=-1;i++){ //需要n-1次寻找最小边
k=Minimum(closedge,); //最小结点下标
printf("%3c城市--%c城市%8d\n",closedge[k].vexadj,[k],closedge[k].lowcost);
s=Seek(closedge[k].vexadj);
fprintf(fp1,"%2d",s);
fprintf(fp1,"%2d",k);
minprice+=closedge[k].lowcost;
closedge[k].lowcost=0; //选过后的结点标记为0
//新顶点并入U后从新选择最小边
for(j=1;j<=;j++){
if([k][j].adj<closedge[j].lowcost){
closedge[j].vexadj=[k];
closedge[j].lowcost=[k][j].adj;
}
}
}
fclose(fp1);
printf("\n\n※使用prim算法得到的最小生成树的代价为: %d ※\n",minprice);
}
int Seek(char c){
int i,k=65;
char s[30];
for(i=1;i<30;i++){
s[i]=(char)k;
k++;
}
for(i=1;i<30;i++){
if(c==s[i])
return i;
}
return 0;
}
/*求出T的下个结点，第k结点
返回最小边的端点*/
int Minimum(Edge closedge[],int n){
int i,j;
int min=INFINITY;
for(i=1;i<=n;i++){
if(closedge[i].lowcost!=0){ //从权值不为0的边中找最小权值
if(closedge[i].lowcost<min){
min=closedge[i].lowcost;
j=i;
}
}
}
return j;
}
/*使用prim算法从顶点u出发构建最小生成树T，并输出T的各条边----无辅助结构体
将结构体变成了两个数组，一个存储最小字符对应的位置，一个判断是否遍历过*/
void MinTree_Prim2(MGraph G,VertexType u){
int i,j,k;
int start[MAX+1]; //0单元弃用 辅助数组
int mark[MAX+1]; //标记该顶点是否加入T中
int minprice=0; //距离
k=Locate_vexM(G,u);
//初始化start和mark数组
for(i=1;i<=;i++){
start[i]=k;
//将遍历过的点标记为1
if(i!=k)
mark[i]=0;
else
mark[i]=1;
}
printf("使用prim算法得到的最小生成树的各边及其权值为:\n\n");
printf(" 城市 权值\n");
for(i=1;i<=-1;i++){
k=Minimum2(G,start,mark);
printf("%3c城市--%c城市%8d\n",[start[k]],[k],[start[k]][k].adj);
minprice+=[start[k]][k].adj;
mark[k]=1; //标记
for(j=1;j<=;j++){
if(mark[j]!=1){
if([k][j].adj<[start[j]][j].adj) //新的点到各个点的距离是否比原先的短
start[j]=k;
}
}
}
printf("\n\n※使用prim算法得到的最小生成树的代价为: %d ※\n",minprice);
}
//求出T的下个结点，第k结点
//返回最小边的端点
int Minimum2(MGraph G,int start[],int mark[]){
int i,j;
int min=INFINITY;
for(i=1;i<=;i++){
if(mark[i]!=1&&[start[i]][i].adj<min){
min=[start[i]][i].adj;
j=i;
}
}
return j;
}
/*kruskal算法运用并查集知识*/
void MinTree_Kruskal(FILE *fp2,MGraph G){
KEdge h[MAXNUM]; //存储边信息
int fat[MAX]; //fat[i]存储i的前驱结点 ---防止闭环
int x,y;
int i,j,k=1; //k==边数
int has=0; //已经连接了多少条边
int minprice=0;
fp2=fopen("C:\\Users\\86151\\Desktop\\help\\","w");
//初始化h[]--上三角当中不等于无穷的数
for(i=1;i<=;i++){
for(j=i+1;j<=;j++){
if([i][j].adj<=100){
h[k].a=i; //行
h[k].b=j; //列
h[k].w=[i][j].adj;
k++;
}
}
}
//初始化fat[]
for(i=1;i<=;i++){
fat[i]=i;
}
//kruskal思想，排序权值
Sort(h,); //对h[]权值升序排序
printf("使用kruskal算法得到的最小生成树的各边及其权值为:\n\n");
printf(" 城市 权值\n");
for(i=1;i<=;i++){
if(has==-1) break;//树的边数等于顶点-1
x=Root(h[i].a,fat); //寻找根结点
y=Root(h[i].b,fat); //寻找根结点
if(x!=y){ //不在一个集合
Unionn(x,y,fat); //fat[y]=x
printf("%3c城市--%c城市%8d\n",[h[i].a],[h[i].b],h[i].w);
fprintf(fp2,"%2d",h[i].a);
fprintf(fp2,"%2d",h[i].b);
minprice+=h[i].w;
has++;
}
}
printf("\n\n※使用kruskal算法得到的最小生成树的代价为: %d ※\n",minprice);
}
//按权值排序
//使用选择排序--升序
void Sort(KEdge h[],int n){
int i,j;
KEdge temp; //定义一个KEdeg结构体作为交换中间变量
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
if(h[i].w>h[j].w){ //交换KEdge数据结构类型
temp=h[i];
h[i]=h[j];
h[j]=temp;
}
}
}
}
/*寻找x的根结点，当一个结点的前一结点是它本身，说明就是根结点*/
int Root(int x,int fat[]){
if(fat[x]!=x)
return Root(fat[x],fat);
else
return x;
}
/*加入集合，并查集的一部分*/
void Unionn(int x,int y,int fat[]){
fat[y]=x;
}
void GraphicsTree(FILE *fp,MGraph *G,Graphics *H){
int i,j;
fp=fopen("C:\\Users\\86151\\Desktop\\help\\","w");
fprintf(fp,"%d",G->vexnum);
fprintf(fp,"\r");
for(i=1;i<=G->vexnum;i++){
printf("请输入第%d个城市的横纵坐标 {(x,y)| x<640,y<480 }:\n",i);
scanf("%d %d",&H[i]->x,&H[i]->y);
fprintf(fp,"%3d ",H[i]->x);
fprintf(fp,"%3d ",H[i]->y);
}
fprintf(fp,"\r");
for(i=1;i<=G->vexnum;i++){
for(j=i+1;j<=G->vexnum;j++){
if(G->arcs[i][j].adj!=0&&G->arcs[i][j].adj<=100){
fprintf(fp,"%2d",i);
fprintf(fp,"%2d",j);
fprintf(fp,"%3d",G->arcs[i][j].adj);
}
}
}
fclose(fp);
}
int main(){
int x,t=1;
MGraph G;
Graphics H;
FILE *fp=NULL,*fp1=NULL,*fp2=NULL;
printf("★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
printf("★ ★\n");
printf("★ **************************************** ★\n");
printf("★ /*欢迎使用最小生成树系统*/ ★\n");
printf("★ **************************************** ★\n");
printf("★ ★\n");
printf("★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n\n\n");
GreateUDN_M(&G);
system("pause");
system("cls");
circular:
while(t){
printf(" * ******************************************************************** *\n");
printf(" * ≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌ *\n");
printf(" * ≌ *主菜单* ≌ *\n");
printf(" * ≌ ≌ *\n");
printf(" * ≌ *1.输出距离网的邻接矩阵 ≌ *\n");
printf(" * ≌ *2.使用prim算法实现最小生成树 ≌ *\n");
printf(" * ≌ *3.使用prim算法实现最小生成树(另一种) ≌ *\n");
printf(" * ≌ *4.使用kruskal算法实现最小生成树 ≌ *\n");
printf(" * ≌ *5.以图形方式输出城市的图 ≌ *\n");
printf(" * ≌ *6.以图形方式输出prim方法找到的最小生成树 ≌ *\n");
printf(" * ≌ *7.以图形方式输出kruskal方法找到的最小生成树 ≌ *\n");
printf(" * ≌ *0.退出 ≌ *\n");
printf(" * ≌ ≌ *\n");
printf(" * ≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌≌ *\n");
printf(" * ******************************************************************** *\n");
printf("请输入您要进行的操作:");
scanf("%d",&x);
//对客户进行容错处理
if(x<0||x>7){
printf("\n请检查输入的数字，并重新输入！！\n\n");
system("pause");
system("cls");
goto circular;
}
switch(x){
case 1:
//system("cls");
printUDN_M(G);
system("pause");
system("cls");
break;
case 2:
//system("cls");
MinTree_Prim(fp1,G,[2]);
system("pause");
system("cls");
break;
case 3:
//system("cls");
MinTree_Prim2(G,[2]);
system("pause");
system("cls");
break;
case 4:
//system("cls");
MinTree_Kruskal(fp2,G);
system("pause");
system("cls");
break;
case 5:
GraphicsTree(fp,&G,&H);
system("pause");
system("cls");
break;
case 6:
printf("\n请移步到第二个程序查看！\n\n");
system("pause");
system("cls");
break;
case 7:
printf("\n请移步到第二个程序查看！\n\n");
system("pause");
system("cls");
break;
case 0:
t=0;
break;
}
}
return 0;
}总结
文章核心代码参考/qq_47733361/article/details/107127316
以上就是最小生成树的具体代码实现，如果不想要图画的生成，只需将文件和主函数中五六七的步骤删除即可，希望能帮助到大家！