管道铺设的最佳方案选择.doc

发布时间：2022-06-16 发布人：admin 分类：说明书资料大小：0.11M 资料格式：doc 举报版权申诉

b56db002-3575-4e31-bfa5-041822254fff.doc.pdf-第1页.png

第1页 / 共14页

b56db002-3575-4e31-bfa5-041822254fff.doc.pdf-第2页.png

第2页 / 共14页

b56db002-3575-4e31-bfa5-041822254fff.doc.pdf-第3页.png

第3页 / 共14页

b56db002-3575-4e31-bfa5-041822254fff.doc.pdf-第4页.png

第4页 / 共14页

b56db002-3575-4e31-bfa5-041822254fff.doc.pdf-第5页.png

第5页 / 共14页

b56db002-3575-4e31-bfa5-041822254fff.doc.pdf-第6页.png

第6页 / 共14页

b56db002-3575-4e31-bfa5-041822254fff.doc.pdf-第7页.png

第7页 / 共14页

b56db002-3575-4e31-bfa5-041822254fff.doc.pdf-第8页.png

第8页 / 共14页

2．设计要求

一、实习目的通过本次实习，更进一步掌握编程的细节问题以及知道在做一些大程序时需要注意的问题，熟练掌握数据结构中的算法，并加强对算法在现实生活中的应用。二、课程设计题目 1、问题描述需要在某个城市的 n 个居民区之间铺设煤气管道，则在这 n 个居民区之间只要铺设 n-1 条管道即可。假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同。选择最优的施工方案能使总投资尽可能少，这个问题即为求网的“最小生成树”。 2．设计要求网采用邻接矩阵为存储结构，以顶点对（i,j）的形式输出最小生成树的边。 3．测试数据 A 18.2 I 44.6 12.1 8.7 H 52.5 32.8 B 5.9 C 56.4 10.5 G 79.2 21.3 D 41.1 67.3 E 98.7 85.6 F

三、算法设计思想 Prim 算法求最小生成树的主要思想：此算法是普里姆与 1957 年提出的一种构造最小生成树的算法，主要思想是：假设 N=（V，{E}）是连通网，TE 是 N 上最小生成树中边的集合。算法从 U={u0}( u0∈V),TE={}开始，重复执行下述操作：在所有 u∈U,v∈V-U 的边（u,v）∈E 中找一条代价最小的边（u0,v0）并入集合 TE，同时 v0 并入 U，直至 U=V 为止。此时 TE 中必有 n-1 条边，则 T=（V，{E}）为 N 的最小生成树。对于最小生成树问题，最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。四、程序模块主函数 main() createg();构造无向图 printfgraph();输出邻接矩阵 MiniSpanTree(); 求最小生成树 locatevex(); 找节点编号 minimum(); 管道权值最小边

五、源程序代码 #include #include #define OK 1 #define MAX_CITIZENS_NUM 30 //最多居民区，即无向图中最大顶点数 #define INFINITY 99.0 typedef int Status; typedef char vertextype; typedef float vrtype; //求最小生成树中所用辅助数组的结构体定义 typedef struct { vertextype adjvex; vrtype lowcost; }closedge[ MAX_CITIZENS_NUM]; typedef struct arccell //邻接矩阵的结构体类型定义 {

vrtype adj; }arccell,adjmatrix[MAX_CITIZENS_NUM][MAX_CITIZENS_NUM]; typedef struct //图的结构体类型定义 { vertextype vexs[MAX_CITIZENS_NUM]; adjmatrix arcs; int vexnum,arcnum; }graph; int locatevex(graph G,char v) //找到输入的顶点在 G.vexs[]中的位置，返回编号 { } int i; for (i=0;i=G.vexnum) return -1; return i; Status createg(graph* G) //构建无向图

{ int m,i,j,k; float w; char v1,v2; printf("请输入居民区总数，以及每个点可以铺设的管道数目:"); scanf("%d %d",&G->vexnum,&G->arcnum); getchar(); for(m=0;mvexnum;m++) { printf("请输入第%d 个居民区代表的字符:",m+1); scanf("%c",&G->vexs[m]); getchar(); } for(i=0;ivexnum;i++) //初始化邻接矩阵 for(j=0;jvexnum;j++) G->arcs[i][j].adj=INFINITY; printf("请输入各条管道所依附的两个居民区及其权值（空格间隔）：\n"); for(k=0;karcnum;k++) { scanf("%c %c %f",&v1,&v2,&w);

getchar(); i=locatevex(*G,v1); j=locatevex(*G,v2); G->arcs[i][j].adj=G->arcs[j][i].adj=w; } return OK; } Status printfgraph(graph G) //在屏幕上输出邻接矩阵存储的无向图 { int i,j; printf("**************************************** \n"); printf("输出的邻接矩阵为：\n"); printf("---99.0 代表无穷大 ---\n"); for(i=0;i

printf("\n"); } return OK; } static int minimum(closedge hp,graph G) //找到管道权值最小的边，返回其在辅助数组中的序号 { float min; int i=0,j,k; while(!hp[i].lowcost) i++; min=hp[i].lowcost; k=i; for(j=i+1;j0&&hp[j].lowcost

return k; } void MiniSpanTree(graph G,vertextype u) //在无向图中找到最小生成树，即代价最小的管道铺设路线 { int i,j,k; closedge help; k=locatevex(G,u); printf ("从居民区 A 出发：\n"); for(j=0;j

分享到：

赞收藏

资料库

管道铺设的最佳方案选择.doc

相关推荐

行业

热门标签

最新资料