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

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(\ while(G.e>(G.n-1)*G.n/2) {

printf(\输入错误,请重新输入:\\n\

12

的建立

阵 scanf(\ }

printf(\请输入该图的顶点信息:\\n\ for(i=1;i<=G.n;i++) {

getchar();

scanf(\ }

for(i=1;i<=G.n;i++) for(j=1;j<=G.n;j++) G.edges[i][j].w=0;

printf(\请输入该图每条边对应的两个顶点的名称:\\n\ for(k=1;k<=G.e;k++) {

scanf(\

printf(\请输入第%d条边的顶点序号：\ scanf(\

printf(\请输入第%d条边的权值大小：\ scanf(\

for(i=1;ch1!=G.vexs[i];i++); for(j=1;ch2!=G.vexs[j];j++); e[p].vexh=i;

13

e[p].vext=j;

e[p].weight=G.edges[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

最小成树生