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

摘要
设计了一个用C/C++编写程序实现克鲁斯卡尔最小生成树算
法，该程序操作简单，界面清晰，易于为用户所接受。
关键词：克鲁斯卡尔，邻接矩阵，最小生成树，VC++。
目录
课题描述 1
问题分析和任务定义 2
逻矩阵。最后在完 成图的信息输入即建立图以后输出图的邻接矩阵表。
•模块二：求图的最小生成树。
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 (i<G->n)
{
min=MaxVertexNum;
for (j=0;j<G->e;j++)
{
if (e[j].weight<min&&e[j].flag==0)
{
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;i<G->e;i++)
if (e[i].flag==1)
p r i n t f ( " (%d,%d) %d \ n " ,e[ i ].vexh,e[ i ].vex t ,e[ i ].we i gh t ) ; //输
出最小生成树
}
该步骤应用的是克鲁斯卡尔算法，它的基本思想是：每次选不 属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入
MST (Minimum Spanning Tree最小生成树)，并将所在的2个连通分
量合并，直到只剩一个连通分量。
所示。
[iB)
口
请输入该图每 条边对应的两 个顶点的名称
请输入该 图的顶点 数和边数-
输入错
误，请重
新输入
请输入该 图的顶点
get char(); scanf("%c",&
.we
e[p」.vexh=i : e[p]. e[p] //权值 e[p].flag=0:
请输入第%d条边的顶点 序号
请输入第%d条边的权值 大小
i++
( 、

i<=G->n
t[i].data=G-
>vexs[i]; t[i].jihe=i;
min=MaxVertexNum;
j=0
e[j].weight<m in&&
-■••q j].flag==0"
min=e[j].weight; k=j；
t[e[k].vexh].ji
e[k] flag=2
e[k].flag=1
"/'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++；
i++
输出最小
生成树
结束
图
程序编码
#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[MaxVer texNum][MaxVer