图论 最小生成树在城市交通建设中的应用.docx

最小生成树在城市交通建设中的应用

姓 名 XX
学 号 S100203029

专 业 计算机应用技术

2010年12月4

目录

摘 要 I
绪论 1
2 有关最小生成树的概念 2
3 prim算法介绍 3
4 系统设计及其应用 5
一、系统设计 5
二、最小生成树应用 6
5 总结 9
参考文献 10
附件： 11

最小生成树在城市交通建设中的应用
摘 要
连通图广泛应用于交通建设，求连通图的最小生成树是最主要的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。
求图的最小生成树有两种算法，一种是Prim（普里姆）算法，另一种是Kruskal（克鲁斯卡尔）算法。
本文通过将城市各地点转换成连通图，再将连通图转换成邻接矩阵。在Microsoft Visual C++上，通过输入结点和权值，用普里姆算法获得权值最小边来得到最小生成树，从而在保证各个地点之间能连通的情况下节省所需费用。
本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。

关键字：PRIM算法、最小生成树、邻接矩阵、交通建设

绪论
中国国际工程咨询公司交通业务部主任周晓勤指出，“以前的各专业规划主要是按照本行业交通发展的需求进行研究和规划的，在交通设施总量不足、基本网不完善的时候，互相之间的矛盾并不突出。但随着多种运输方式设施建设的快速发展，各行业交通网络的逐步完善，多种运输方式网络之间的叠加，难免显现出各种运输方式在通道和枢纽衔接上的不协调。其结果是，资源浪费，效率低下，使用不便利。而综合交通网发展规划的颁布有利于运输整体结构的调整，资源节约和集约利用，对于交通运输业的可持续发展具有重要和深远的意义。”
在社会主义建设时期，各个城市建设问题尤其是交通建设尤为重要。在保证各个城市能互相连通的情况下，怎么保证建设公路，怎么建设最省钱是建设工程公司所需考虑的重大情况。从而能节省更多的钱来投资其他地方建设，如农村交通建设。
各个农村交通建设好之后，则可再根据将农村作为一个结点和其它农村再次运用最小生成树。
最小生成树则能有效的解决此问题。例如，以尽可能低的总价建设若干条高速公路，把n个城市联系在一起。
普里姆算法通过寻找无向图中权值最小的边，并且将其组合成最小生成树，同时将最小生成树以点集的形式输出，便于观察。
根据课程设计任务书要求，本系统开发主要完成以下功能和性能。
(1) 输入无向图的方式要尽量简单方便。
(2) 要能够形象方便的观察无向图的结构。
(3) 要能够形象地演示PRIM算法求最小生成树的过程。
本文第二章主要介绍图和最小生成树、邻接矩阵等概念。第三章主要介绍prim算法。第四章进行系统设计与调试及其在交通建设中的应用。

2 有关最小生成树的概念
最小生成树：连通加权图里权和最小的生成树称为最小生成树。
从最小生成树定义看主要先了解图、树及生成树。本文中最小生成树在计算机中存储方法是应用邻接矩阵的形式存储。故也应了解邻接矩阵的定义。
定义一（图）：图是有一个非空的顶点集合和一个描述顶点之间的关系即边的集合组成。它可以形式化的定义为：
G=(V,E)
V={ | VertexType}
E={<,>|,∈V∧P(,) }
其中，G表示一个图，V是图G中顶点的集合，E是V中顶点偶对的有限集，这些顶点偶对称为边，VertexType是用于描述顶点类型，集合E中P(,)的含义是：对有向图来说用“<>”表示，对无向图来说用“（）”表示，即从到 两个顶点之间存在边。
定义二（树）：树包含n（n>=0）个节点。当n=0时表示为空树。其定义如下：
T=(D,R)
其中，D为树中节点的有限集合，关系R满足一下条件：
1） 有且仅有一个节点k0属于D，它对于关系R来说没有前趋节点，结点k0称作树的根结点。
2） 除根结点k0之外，D中的每个结点仅有一个前趋结点，但可以有过个后继结点。
3） D中可以有多个终端结点。
即除根结点无父结点，其余各结点都有一个父结点和n（n>=0）个子结点。

图的矩阵表示，本文中只用到了邻接矩阵，故在这只提出邻接矩阵的定义，及其图在邻接矩阵中的表示。
设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.edge[n][n]，　　用来存放顶点的信息和边或弧的信息。
定义三（邻接矩阵（Adjacency Matrix））：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：（本文主要为无向图的邻接矩阵）
（1） 无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。
（1）无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，可以表示为某一具体应用的数据。也表示i结点是否与j结点连通。

定义四（生成树）：如果T是G的一个生成子图又是一棵树，则称T是图G的一棵生成树。

3 prim算法介绍
最小生成树的两个著名算法：prim算法[和克鲁斯卡尔算法[2] ,本文应用的是prim算法。则克鲁斯卡尔算法则不进行描述了。
Prim算法的基本思想：首先，选择带最小的边，把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联，并且不与已在数理的边形成圈，当已经添加了n-1条边为止。
PRIM算法介绍：设图中顶点的全集为V, U中存放已选中过的点,用数据结构closedge[]存放选择需要的数据,先把下标0对应点放入U中, closedge[i].uxiabiao=0,(因为U中只有下标0这一个点), closedge[i].lowcost中存放其他点到下标为0的点的权,closedge[0].lowcost=0;表示下标为0的点已在U中了。在closedge按顺序找到最先不在U中,且与U中点直接相连的点,把此边的权赋给min，用擂台式比较法选出closedge[j].lowcost中最小的,此时min中存放的是最小值所在下标,也就是下一个要放入U中的点的下标。输出选中的这条边，它是最小生成树中的一条边。因为U中又加入了一个点，所以要修改closedge[i].lowcost的值，比较新选中点与V-U中点的权和原来的closedge[i].lowcost,取小的那个存入。然后继续如上的选择,循环vexnum-1次,就选出了最小生成树中的vexnum-1条边。本程序采用数组存储结构进行存储，把第一个点所到的边记录下来，然后把权值最小的边存入数组，同时将刚才所存边的的终点作为起点再次记录该点所到的边，并记录权值最小的边存入数组，这个过程中，已经被访问的点不再访问。知道最后所有的权值最小的边全部输出。这就是PRIM算法求最小生成树。
Prim算法有两种形式，其伪代码如下：
算法一：
procedure Prim;
begin
T:=Φ；
U:={1};
while U<>V do
begin
(u,v):= u∈U且v∈V-U的最小权边;
T:=T∪{(u,v)};
U:=U∪{v};
end;
end;
改进的prim算法2如下：
procedure Prim(var G:adj_matrix;size:integer);{G为图，size为图的节点数目;注意：假设输入的图是连通图}
var
lowcost:array [1..maxsize] of integer;
used:array [1..maxsize] of boolean;
closeset:array[1..maxsize] of integer;
i,j,k,min:integer;

begin
for i:=2 to size do {初始化，此时U只含有顶点1}
begin
lowcost[i]:= G[1,i];
closeset[i]:=1;
used[i]:=false;
end;
used[1]:=true;
for i:=2 to size do
begin
min:=maxint;
j:=i;
for k:=2 to size do {用选择法寻找顶点分别在V-U与U中权最小的边}
if (not used[k])and(lowcost[k] begin
min:=lowcost[k];
j:=k;
end;
writeln(fout,'(',closeset[j],',',j,')'); {输出找到的最小生成树的一条边，此处可根据情况修改}
used[j]:=true; {将j填加到U}
for k:=2 to size do {调整lowcost和closeset}
if (not used[k])and(G[j,k] begin
lowcost[k]:=G[j,k];
closeset[k]:=j;
end;
end;
end;

4 系统设计及其应用
一、系统设计
数据信息以结构体【3】【4】和数组形式储存，结点的信息结构体定义如下：
struct graph
{
char tnode;
char hnode;
double quanzhi;
}gr[100];
char node[50]=" ";
图的存储结构为：
#define INFINITY INT_MAX //最大值
#define MAX_VERTEX_NUM 20 //最多的顶点个数
typedef enum{DG,DN,UDG,UDN} GraphKind;
//{有向图、有向网、无向图、无向网}
typedef struct ArcCell{
VRType adj; //顶点关系类型：图：0、1 网：权值
InfoType *info;//该弧相关信息指针
}ArcCell,AdjMaTrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM];
typedef struct{
VertexType vexs[MAX_VERTEX_NUM];//顶点向量
AdjMaxtrix arcs; //邻接矩阵
int vexnum,arcnum; //顶点数和弧或边数
GraphKind kind; //图的种类标志
}Mgraph;
Prim算法：
void prim(mgraph g,int k,int n) //核心算法Prim算法实现函数
{
int i,j,min,p; //定义整型变量i,j用于循环 min和p分别用于临时存放最小权值及其下标
struct //定义型类型数据closedge[]用于临时存放下标和最小边
{
int adjvex;
int lowcost;
}closedge[100];
for(i=1;i<=n;i++) //初始化辅助数组
if(i!=k)
{
closedge[i].adjvex=k;
closedge[i].lowcost=g.v[k][i];
}
closedge[k].lowcost=0; //将节点加入生成树中
for(i=1;i<n;i++) //循环比较最小权值且将最小权值的点加入生成树中并打印输出
{
p=1; //初始化p
min=maxvalue; //初始化最小权值
for(j=1;j<=n;j++) //循环n次比较最小权值
if(closedge[j].lowcost!=0&&closedge[j].lowcost<min) //当前节点不在已生成树中且权值最下
{
min=closedge[j].lowcost; //替换最小权值为当前节点的权值
p=j; //记录该节点下标
}

printf("%d_ _%d\n",closedge[p].adjvex,p,min); //打印最小的权值的下标和最小边
closedge[p].lowcost=0; //将该节点加入生成树中
for(j=1;j<=n;j++) //刷新临时存放空间
if((g.v[p][j]) < (closedge[j].lowcost))
{
closedge[j].lowcost=g.v[p][j]; //赋值最小边
closedge[j].adjvex=p; //赋值最小边对应下标
}
}

二、最小生成树应用
C编写的程序测试【5】数据：假设如图
V2

V3

V5

V7

V1

V6

V4

3
4
3
5
7
4
1
5
1
6
3
6

结果应该如下
V3

V5

V7

V1

V6

V4

5
1
1
3
V2

2
3

程序运行如图：

5 总结
该算法循序渐进，通过数组的灵活应用，构造无向连通图并最终轻松实现了生产最小生成树的目的。实验表明最小生成树能具体应用到交通建设上去。这个程序还有待开发，将其运用到交通建设上，能起到节约资源和时间的作用，并且也是交通建设发展必要的工具。

参考文献
【1】《数据结构与算法教程》第二版，李春葆等，清华大学出版社。
【2】《图论及其算法》，殷剑宏等，中国科学技术大学出版社。
【3】《C语言程序设计》(第三版)，谭浩强，清华大学出版社。
【4】《数据结构》(C语言版)，严蔚敏 吴伟民，清华大学出版社。
【5】《c语言习题集与上机指导》第二版，谭浩强，高等教育出版社。

附件：
程序代码：
#include "stdio.h"
#define maxnum 10
#define maxvalue 88
typedef struct //定义存放各节点间边的权值的二位数组为新的数据类型可称为图
{
int v[maxvalue][maxvalue];
} mgraph; //该数据类型用标识符mgraph表示
mgraph input(int n) //数据输入函数用于输入各节点间边的权值
{
mgraph x; //定义x为mgraph类型
while(n<=0||n>maxnum) //控制输入出错重新执行
{
printf("输入有误,请重新输入:");
scanf("%d",&n);
}
for(int i=1;i<=n;i++) //双层循环控制每个节点到其他各节点的权值
{
for(int j=0;j<=n;j++)
{
int temp; //定义临时变量用于存放输入权值便于接下的过滤操作
if(i==j) //各节点到自身的权重赋为0
x.v[i][j]=0;
else
if(i<j) //赋值其他各点到比其大的下标的节点
{
printf("请输入节点%d到节点%d的权:",i,j);
scanf("%d",&temp); //将输入临时存放在temp
while(temp==0||temp<-1) //过滤输入数据
{
printf("输入有误,请重新输入:\n");
printf("请输入%d到%d的权:",i,j);
scanf("%d",&temp);
}
if(temp>0) //将符合要求数据赋值给temp
x.v[i][j]=temp;
else //temp=-1时将权重赋值最大值88
x.v[i][j]=maxvalue;
}
else //i>j由于权重是对称的即呈上三角或下三角分布故只需将i,j对换即可
x.v[i][j]=x.v[j][i];
}
printf("\n");
}
return x; //返回图x
}
void print(mgraph g,int n) //打印函数
{
int i,j; //定义整型i,j
printf(" "); //打印美观需要
for(i=1;i<=n;i++)
printf("%2d ",i);
printf("\n");
for(i=1;i<=n;i++) //双层循环按矩阵方式打印输出各节点间权值
{
printf("%d ",i);
for(j=1;j<=n;j++)
printf("%2d ",g.v[i][j]);
printf("\n");
}
}
void prim(mgraph g,int k,int n) //核心算法Prim算法实现函数
{
int i,j,min,p; //定义整型变量i,j用于循环 min和p分别用于临时存放最小权值及其下标
struct //定义型类型数据closedge[]用于临时存放下标和最小边
{
int adjvex;
int lowcost;
}closedge[maxnum];
for(i=1;i<=n;i++) //初始化辅助数组
if(i!=k)
{
closedge[i].adjvex=k;
closedge[i].lowcost=g.v[k][i];
}
closedge[k].lowcost=0; //将节点加入生成树中
for(i=1;i<n;i++) //循环比较最小权值且将最小权值的点加入生成树中并打印输出
{
p=1; //初始化p
min=maxvalue; //初始化最小权值
for(j=1;j<=n;j++) //循环n次比较最小权值
if(closedge[j].lowcost!=0&&closedge[j].lowcost<min) //当前节点不在已生成树中且权值最下
{
min=closedge[j].lowcost; //替换最小权值为当前节点的权值
p=j; //记录该节点下标
}
printf("%d_ _%d\n",closedge[p].adjvex,p,min); //打印最小的权值的下标和最小边
closedge[p].lowcost=0; //将该节点加入生成树中
for(j=1;j<=n;j++) //刷新临时存放空间
if((g.v[p][j]) < (closedge[j].lowcost))
{
closedge[j].lowcost=g.v[p][j]; //赋值最小边
closedge[j].adjvex=p; //赋值最小边对应下标
}
}
}
int main() //主函数
{
int n,start; //定义整型n,start表示节点数和开始节点
printf("请输入节点数(不大于10):");
scanf("%d",&n);
mgraph red; //定义图red
red=input(n); //调用输入函数用户输入数据
print(red,n); //调用输出函数打印输出所输入的数据
printf("请输入开始节点:");
scanf("%d",&start);
prim(red,start,n); //调用prim函数实现prim算法求最小生成树
return 0;
}