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

.
.
摘 要
设计了一个用C/C++编写程序实现克鲁斯卡尔最小生成树算法，该程序操作简单，界面清晰，易于为用户所承受。
关键词：克鲁斯卡尔，邻接矩阵，最小生成树，vc++。
.
.
.
.
目 录
1 课
e[p].vexh=i;
e[p].vext=j;
e[p].weight=[i][j].w=ch3; //权值
e[p].flag=0;
p++;
}
return G;
}

创立图使用的是函数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 (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)
printf("(%d,%d) %d\n",e[i].vexh,e[i].vext,e[i].weight);//输出最小生成树
}
该步骤应用的是克鲁斯卡尔算法，它的根本思想是：每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边参加MST〔Minimum Spanning Tree最小生成树〕，并将所在的2个连通分量合并，直到只剩一个连通分量。
。
.
.

.
.

.
.
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;
.
.
int jihe;
}VEX;
typedef struct
{
int vexh,vext; //边顶点
int weight; //权值
int flag; //标记
}EDGE;
EDGE e[M];
int p=0;
/*************************图邻接矩阵的建立**************************/
MGraph C