实验三：管道铺设施工的最佳方案问题
一、问题描述
1、实验题目：
需要在某个城市n 个居民区之间铺设煤气管道，则在这n 个居民小区之间只需要铺设n-1条管道即可。假设任意两个校区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。 2、基本要求：
在可能假设的m 条管道中，选取n-1条管道，使得既能连同n 个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。 3、测试数据：
使用下图给出的无向网数据作为程序的输入，求出最佳铺设方案。
图为小区煤气管道铺设网及其参考解
数据输入与输出：从键盘或文件读入上图中的无向网，以顶点对（i ，j ）的形式输出最小生成树的边。 二、需求分析
1、本程序通过用户提供的信息，可给出n 个小区之间的管道铺设的最佳路径。
98.7
44.6
41.1 10.5
12.1
A
I D
B
C
E
G
F
H
32.8
85.6
67.3
21.3 5.9
18.28.7
52.5 56.4 79.2
5.9
32.8
12.1
8.7
79.2
B
I H
F
E
D
C A
41.1 21.3 10.5
G
2、当用户输入必要的信息完毕后，提示用户输入小区的起点。
3、程序将自动给出以某个小区作为起点的最佳路径。 三、概要设计 1、设计思路
这是一个运筹学中的规划问题，求解最佳方案。先选一个点作为起点，从这个点选取费用最小的一条路径。算法的基本思想是：对于图G=(V,E)，V 是包含n 个顶点的顶点集，E 是包含m 条弧的弧集，（v,w ）是E 中从v 到w 的弧，c(v,w)是弧（v,w ）的非负权值，设s 为V 中的顶点，t 为V 中可由s 到达的顶点，则求解从s 至t 的具有最小弧权值和的最短路径搜索过程如下： ①将v 中的顶点分为3类：已标记点、未标记点、已扫描点。将s 初始化为已标记点，其他顶点为未标记点。为每个顶点v 都建立一个权值d 和后向顶点指针p,并将d 初始化如下：d(v)=0,v=s;d(v)= ∞，v ≠s 。
②重复进行扫描操作：从所有已标记点中选择一个具有最小权值的顶点v,并将其设为已扫描点，然后检测每个以v 为顶点的弧（v,w ）,若满足d(v)+c(v)对于无向网络，采用邻接表的结构存储。 ①抽象数据类型
ADT R[N]{
数据对象：D={ i a |i a ∈int, i=1,2,3.... } 数据关系：R=φ }}ADT R[N]
定义一个数组a[],存储任意两点之间的权值。
定义一个数组b[],每个数组元素表示当前所找到的从始点vi 到vk 最小费用的值。它的初态为：若从vi 到vj 有边，则为边的权值；否则置为∞。 定义一个数组fee[]，其元素fee[k]用以记录vi 到vk 最短路径中vk 的直接
前驱结点的序号，如果vi到vk存在边，则fee[k]初值为i。
定义一个数组tag[],记录某个顶点是否已计算过最小费用，如果tag[k]=0,则vk∈V-S,否则vk∈S。初始值除tag[i]=1外，所有值均为0。
②边表结点结构体
EdgeNode//边表结点
{
定义一个访问标记bool flag;
顶点域char name;
顶点所能达到的结点char s_name;
边上信息double fee;
结点的指针域EdgeNode *next;
};
③顶点表结构体
Vnode//顶点表结点
{
顶点域char vname;
边表的头指针EdgeNode *firstedge;
};
④无向网图的结构体
Algraph
{
邻接表类型的数组Vnode AdjList[MaxV erNum];
邻接表的顶点数与边数int n,e;
};
⑤自定义函数
void Create_Algraph(Algraph *G)//创建无向网图
{
根据边及顶点的个数
for()
{ 申请空间，并将相应的信息填入空间中}
}
void Print_Algraph(Algraph *G)；//以邻接表的存储形式打印出网络的信息void Change_Flag(Algraph *G,char name)
{ 若结点被访问，就将flag修改为１；}
EdgeNode *Min_Fee(Algraph *G,char name)//求去最小费用的函数
{
对于一个顶点，若与其相连的顶点的费用，都被访问过（即flag=1）
那么就返回该结点的上一级结点
如果至少有一条路径没被访问，那么就将最小费用的结点返回；
}
void Min_Tree(Algraph *G,Vnode *V,char name)/*求解最小生成树,name为
最小生成树的根节点*/ {
根据给出的根结点，并调用Min_Fee()函数，求取最小费用，在与其他结点的最小费用相比，在求出最小费用；
将最小费用的结点用链表的形式存储；
}
void Print_MinTree(EdgeNode *N); //打印最小生成树
double Total_Fee(Vnode *V);//计算最小生成树对应的费用
⑥本程序的保护模块：
