发布时间 : 星期六 文章最小生成树的应用数据结构课程设计更新完毕开始阅读355284a60508763230121248
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< } 6