jj.txt

printf(&quot 请输入％d个课程的代表值(<％d个字符): &quot ,(*G).vexnum,MAX_NAME) for(i=0 i<(*G).vexnum ++i)

数据结构》课程设计报告单
【题目】中国道路交通网络信息查询系统
【目的】加深理解线性表,树,图的基本概念及它们的存储,掌握无向图的重要应用——最短路径的算法,广度优先搜索方法的应用,构造最小生成树的算法.
【要求】城市间的距离网采用邻接表表示.要求能:
显示网图
显示邻接表
显示城市间最短路径
显示两城市间最少中转路径
显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价.
【主要内容及实现的功能】给定26个城市间的距离网(p187),用Dijkstra方法求最短路径;广度优先搜索方法显示城市间最少中转路径;用Prim算法建立最小生成树,并计算得到的最小生成树的代价.
【原始数据及资料】参考课本P187
【主要参考资料】
【课程设计报告单】
1,系统设计分析
本系统有三大模块组成:
1,图的存储:图的存储有两种方法a.矩阵法b.邻接法,矩阵发和邻接法两种存储结构的比较如下图
名称
实现方法
优点
缺点
时间复杂度
邻接矩阵
二维数组
1,易判断两点间关系
2,容易求得顶点的度
占用空间大
O(n2+m*n)
邻接表
链表
节省空间
容易求得顶点的出度
不易判断两点间关系
不易求得顶点的入度
O(n+m)或O(n*m)
在本次课程设计中,我们要求使用邻接法,因为本次设计使用的交通图为无向图,使用邻接法可以比矩阵法更节省空间,而且时间复杂度也相对降低.
2,图的遍历:
图的遍历有两种方法a.广度优先b.深度优先.本次设计中要求显示两城市间最少中转路径,而广度优先遍历图的过程是以起点,由近至远,依次访问和起点有路径相通的其它节点.因此,通过广度优先算法可以查询出两个城市间最少中转的路径.
3,最短路径和最小生成树:
交通图的任意两个城市均有一条或多条路径可以相连,通过最短路径,我们可以将两个城市间距离(权值)最短的路径找到并打印出来.最小生成树是求将所有城市相连所需的最短路径.
2,系统设计结构图
1)显示网图
2)显示城市间最短路径(城市代码)
3)显示邻接表
4)显示城市间最短路径(城市名称)
5)两个城市间最短路径(城市代码)
6)两个城市间最少中转路径
7)最小生成树.
3,算法描述(实现思路)
1,最短路径的算法描述:
假设每个点都有一对标号 (dj, pj),其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路),其长度等于零);pj则是从s到j的最短路径中j点的前一点.求解从起源点s到点j的最短路径算法的基本过程如下:
1) 初始化.起源点设置为:① ds=0, ps为空;② 所有其他点: di=∞, pi= ;③ 标记起源点s,记k=s,其他所有点设为未标记的.
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离,并设置:
dj=min[dj, dk+lkj]
式中,lkj是从点k到j的直接连接距离.
3) 选取下一个点.从所有未标记的结点中,选取dj 中最小的一个i:
di=min[dj, 所有未标记的点j]
点i就被选为最短路径中的一点,并设为已标记的.
4) 找到点i的前一点.从已标记的点中找到直接连接到点i的点j*,作为前一点,设置:
i=j
5) 标记点i.如果所有点已标记,则算法完全推出,否则,记k=i,转到2) 再继续.
2,广度优先遍历的算法描述:
设图G的初态是所有顶点均未访问过.在G中任选一顶点v为源点,则广度优先遍历可以定义为:首先访问出发点v,接着依次访问v的所有邻接点w1,w2,…,wt,然后再依次访问与wl,w2,…,wt邻接的所有未曾访问过的顶点.依此类推,直至图中所有和源点v有路径相通的顶点都已访问到为止.此时从v开始的搜索过程结束.
⑴设立初值,并令起始结点进队:
f:=0;r:=1;lL[r]:=st,E[st]:=1;w:=1;h:=1;
⑵将此时第h层(开始h=1,表示第一层)的w(开始时w=1,表示一个结点)顶点的顺序出队,并访问与该层各顶点相邻接但又没有访问过的顶点,同时将这些结点进队列,且设立前趋链接指针和访问过标记,若此时的结点为目标结点,则只设立前趋链接指针而不设立访问过标记
⑶计算此时第h+1层的顶点个数w:=r+1-g[h],然后看该层有多少个顶点为目标结点,凡是出现目标顶点的,就将其个数累计,也就是为最短路径的条数,同时从这个目标结点按前趋链接指针将到达该目标结点的路径的各个顶点编号存入c[s,j]中,然后转⑷,若目标顶点累计个数为0,表明该层没有出现目标结点,则转⑵.
⑷打印搜索到的各条最短路径的各结点编号,并结束程序.
3,最小生成树的算法描述:
求MST的一般算法可描述为:针对图G,从空树T开始,往集合T中逐条选择并加入n-1条安全边(u,v),最终生成一棵含n-1条边的MST.当一条边(u,v)加入T时,必须保证T∪{(u,v)}仍是MST的子集,我们将这样的边称为T的安全边.用伪代码可将算法描述为:
GenerieMST(G){//求G的某棵MST
T〈-￠; //T初始为空,是指顶点集和边集均空
while T未形成G的生成树 do{
找出T的一条安全边(u,v);//即T∪{(u,v)}仍为MST的子集
T=T∪{(u,v)}; //加入安全边,扩充T
}
return T; //T为生成树且是G的一棵MST
}
4,各个模块(函数)的实现功能,所用参数,说明及原始代码.
1)void BFSAL(ALgraph &G,int i)//图的广度优先搜索算法(邻接表存储表示)
2)void CreateALgraph(ALgraph &G)//生成邻接表
3)void printALgraph(ALgraph &G)//显示邻接表
4)void printMgraph(ALgraph &G)//显示图
5)void printpath1(ALgraph &G,int v0)//显示城市间最短路径(代码输出)
6)void printpath2(ALgraph &G,int v0)//显示城市间最短路径
7)void shortestpath(ALgraph &G,int v0)//最短路径算法
8)void MiniSpanTree(ALgraph &G, int v0)//最小生成树
9)int menu(void)//菜单函数