最小生成树的应用数据结构课程设计

int weight; }AdjMatrix[MAX][MAX]; Typedef struct {

djMatrix arc; int vexnum, arcnum; } MGraph;

3．2模块划分

本程序包括五个模块： （1）主函数模块

(2) 邻接矩阵定义模块代码

typedef struct ArcCell{ int adj; char *info; }ArcCell,AdjMatrix[20][20]; typedef struct {

char vexs[20]; AdjMatrix arcs; int vexnum,arcnum; }MGraph_L;

int localvex(MGraph_L G,char v)

{ int i=0; while(G.vexs[i]!=v)

3

{ ++i;} return i;}

(3) 创建链接矩阵模块代码

int creatMGraph_L(MGraph_L &G) { char v1,v2; int i,j,w;

cout<<\创建无向图（城市分布图）…\请输入图G顶点（城市）和弧（边）的个数:(4 6)不包括“()”\ cin>>G.vexnum>>G.arcnum; for(i=0;i!=G.vexnum;++i)

{ cout<<\输入顶点（城市）\

cin>>G.vexs[i]; } for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

{

G.arcs[i][j].adj=int_max;

G.arcs[i][j].info=NULL; }

for(int k=0;k!=G.arcnum;++k)

{ cout<<\输入一条边依附的顶点（城市）和权（距离）:(a b 3)不包

括“()”\ cin>>v1>>v2>>w;

i=localvex(G,v1); j=localvex(G,v2); G.arcs[i][j].adj=w; G.arcs[j][i].adj=w;}

cout<<\图G邻接矩阵创建成功！\ return

4

G.vexnum;}

(4)最小生成树Prim算法及代价模块代码 (5)最小生成树kruskal算法及代价模块代码

4 详细设计

4．1数据类型的定义

（1）树类型

#define MAXVALUE 100 #define MAXLEAF 50

#define MAXNODE MAXLEAF*2-1;

（2）图类型

typedef struct node { int adjvex;

int w;

struct node *nextedge;

}edgenode; typedef struct {

char data; int id; edgenode *firstedge;

}vexnode;

4．2主要模块的算法描述

（1）主函数

algraph gra; MGraph_L G; char a='a'; d=creatMGraph_L(G);

5

int i,d,g[20][20]; vnode v;

cout<

while(y='y') { cout<<\请选择菜单：\ cin>>s; switch(s){

case 0: cout<<\邻接矩阵显示如下：\ ljjzprint(G); break; case 1: for(i=0;i!=G.vexnum;++i)

for(intj=0;j!=G.vexnum;++j) g[i+1][j+1]=G.arcs[i][j].adj; cout<<\ prim(g,d); break; } cout<>y; if(y=='n') break; }

}

6