图的逻辑结构图的存储结构及实现最小生成树最短路径AOV网与拓扑.PPT

路径长度： 路径长度： 回路（环）：第一个顶点和最后一个顶点相同的路径。 简单路径：序列中顶点不重复出现的路径。 简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。 template class DataType MGraphDataType :: MGraph(DataType a[ ], int n, int e) { vertexNum = n; arcNum = e; for (i = 0; i vertexNum; i++) vertex[i] = a[i]; for (i = 0; i vertexNum; i++) //初始化邻接矩阵 for (j = 0; j vertexNum; j++) arc[i][j] = 0; for (k = 0; k arcNum; k++) //依次输入每一条边 { cin i j; //输入边依附的两个顶点的编号 arc[i][j] = 1; arc[j][i] = 1; //置有边标志 } } 首先计算以下与关键活动有关的量： 图的存储结构：带权的邻接矩阵存储结构 数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。 数组path[n]：path[i]是一个字符串，表示当前所找到的从始点v到终点vi的最短路径。初态为：若从v到vi有弧，则path[i]为vvi；否则置path[i]空串。 数组s[n]：存放源点和已经生成的终点，其初态为只有一个源点v。 数据结构 : 6.4 最短路径 1. 初始化数组dist、path和s； 2. while (s中的元素个数n) 2.1 在dist[n]中求最小值，其下标为k； 2.2 输出dist[j]和path[j]； 2.3 修改数组dist和path； 2.4 将顶点vk添加到数组s中； Dijkstra算法——伪代码 6.4 最短路径 每一对顶点之间的最短路径 问题描述：给定带权有向图G＝(V, E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径。 解决办法1：每次以一个顶点为源点调用Dijkstra算法。显然，时间复杂度为O(n3)。 解决办法2：弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法，其时间复杂度也是O(n3)，但形式上要简单些。 6.4 最短路径 基本思想：对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。 Floyd算法 6.4 最短路径 0 4 11 6 0 2 3 ∞ 0 有向网图 邻接矩阵 Floyd算法 a c b 3 4 6 11 2 6.4 最短路径 Floyd算法 a c b 3 4 6 11 2 dist-1 = 0 4 11 6 0 2 3 ∞ 0 path-1 = ab ac ba bc ca 初始化 6.4 最短路径 Floyd算法 a c b 3 4 6 11 2 dist-1 = 0 4 11 6 0 2 3 ∞ 0 path-1 = ab ac ba bc ca 第1次迭代 dist0 = 0 4 11 6 0 2 3 7 0 path0 = ab ac ba bc ca cab 6.4 最短路径 Floyd算法 a c b 3 4 6 11 2 第2次迭代 dist0 = 0 4 11 6 0 2 3 7 0 path0 = ab ac ba bc ca cab