目录
一、课题描述： 二、需求分析 三、总体结构设计 四、各子模块设计 五、编程设计 六、测试结果 七、总结 八、参考文献 附 录
一、课题描述：
设计一张城市地图，图中的顶点为城市，无向边代表两个城市间的 连通关系，边上的权代表公路造价。图中任一对城市都是连通的，用公 路把所有城市联系起来，设计可使得工程的总造价最少。
n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) { parent[n] = m; printf("<< %s, %s >> %d\n", vex[edges[i].begin].name, vex[edges[i].end].name, edges[i].weight); Mincost+=edges[i].weight; } } printf("使各城市间公路总造价的最小费用为： Mincost=%d\n",Mincost); } int Find(int *parent, int f) { while ( parent[f] > 0) { f = parent[f]; } return f; } 3．用冒泡法对公路造价按从小到大的顺序排列 void sort(edge edges[] ,MGraph *G) { int i, j; int temp; for ( i = 1; i < G->arcnum; i++) { for ( j = i+1; j &3;) { if (edges[i].weight > edges[j].weight) { temp = edges[i].begin; edges[i].begin = edges[j].begin; edges[j].begin = temp; temp = edges[i].end;
typedef struct { AdjMatrix arc; int vexnum, arcnum; }MGraph;
时间复杂度0(n^2)
算法描述 该算法是建立一个带权的无向图，并用Kruskal算法求该图的最小生成 树，用父结点和子女结点集的形式输出最小生成树。 1.无向带权图的建立 图的存储结构如上所示，;用adj是否为1判断两城市间是否有公路，adj 为1时表示有公路，反之没有公路，vexnum和arcnum分别表示城市数和 公路数，name和num分别表示城市信息和城市序号，建图的算法如下所 示： void CreatGraph(MGraph *G) { int i, j,n,h,m,k; char u[MAX],v[MAX]; printf("请输入公路数和城市数:"); scanf("%d %d",&G->arcnum,&G->vexnum) for (i = 1; i <= G->vexnum; i++)//初始化图 { for ( j = 1; j <= G->vexnum; j++) {
edges[i].end = edges[j].end; edges[j].end = temp; temp = edges[i].weight; edges[i].weight = edges[j].weight; edges[j].weight = temp; } } }
六、测试结果
城市间公路及其造价的输出结果
N N
Y Y
N N Y Y
N N i<=G->vexnum printf(“<%s,%s> %d\n”,vex…); i++ i<=G->vexnum printf(“<%s,%s> %d\n”,vex…); i++ Y Y
五、编程设计
存储结构 该函数包含三个结构体，即存储城市、存储公路和存储图的结构体，其 结构体分别如下所示： 1.顶点和边的存储表示 用字符串name表示城市信息，num表示城市的序号。 struct node{ char name[10]; int num; }vex[20]; 用整型begin和end表示公路的起点和终点，weight表示公路的造价。 typedef struct { int begin; int end; int weight; }edge; 2.图的邻接矩阵存储表示 用整型adj表示城市间的关系，weight表示公路的造价。 typedef struct { int adj; int weight; }AdjMatrix[MAX][MAX]; 用arc表示邻接矩阵，vexnum和arcnum表示图当前的城市数和公路数。
G->arc[i][j].adj = G->arc[j][i].adj = 0; } } printf("\n请输入城市的信息:"); for(n=1;n<=G->vexnum;n++) { scanf("%s",vex[n].name); vex[n].num=n; } for ( i = 1; i <= G->arcnum; i++) { printf("\n请输入有公路的2个城市:"); scanf("%s",v); scanf("%s",u); for ( k= 1; k <= G->vexnum; k++) { if(strcmp(v,vex[k].name)==0) {m=vex[k].num;} if(strcmp(u,vex[k].name)==0) {h=vex[k].num;} } G->arc[m][h].adj = G->arc[h][m].adj = 1; getchar(); printf("\n请输入%s与%s之间的公路造价:",vex[m].name, vex[h].name); scanf("%d",&G->arc[m][h].weight); } printf("邻接矩阵为:\n"); for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf("%d ",G->arc[i][j].adj); } printf("\n"); }
N N Y Y
N N Y Y
n<=G->vexnum scanf(“%s”,vex[n].name); n++ n<=G->vexnum scanf(“%s”,vex[n].name); n++ N N Y Y
2.用kruskal算法求最小生成树 sort(edges,G) i=1 找公路和公路的造价 j++ i++ j=i+1 j<=G->vexnum i<G->vexnum Int i,j,n,m i=1 sort(edges,G) i=1 找公路和公路的造价 j++ i++ j=i+1 j<=G->vexnum i<G->vexnum Int i,j,n,m i=1
N N Y Y Y N
N
Y Y Y
i<=G->vexnum parent[i]=0; i++ i<=G->vexnum parent[i]=0; i++ N N Y Y
3.用冒泡法排序 printf(“\n公路造价排序为：”) i=1 公路造价排序 j++ i++ j=i+1 j<=G->vexnum i<G->vexnum int i,j; i=1 printf(“\n公路造价排序为：”) i=1 公路造价排序 j++ i++ j=i+1 j<=G->vexnum i<G->vexnum int i,j; i=1
附 录
程序代码 #include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<string.h> #define M 20 #define MAX 20 struct node{ char name[10]; int num; }vex[20]; typedef struct { int begin; int end; int weight; }edge; typedef struct { int adj; int weight; }AdjMatrix[MAX][MAX]; typedef struct { AdjMatrix arc;
三、总体结构设计
功能模块图
无 向 图 的 建 立
最 小 生 成 树 的 求 解
按父 结点 和子 女结 点集 的形 式输 出， 求最 小值,
四、各子模块设计
1.无向图的建立（初始化） printf(“\n请输入城市的信息”) n=1 G->arc[i][j].adj=G->arc[j][i].adj=0 j++ i++ j=1 j<=G->vexnum i<=G->vexnum Int i,j,n,h,m,k i=1 printf(“\n请输入城市的信息”) n=1 G->arc[i][j].adj=G->arc[j][i].adj=0 j++ i++ j=1 j<=G->vexnum i<=G->vexnum Int i,j,n,h,m,k i=1