数据结构课件第6章图幻灯片.ppt

l[i] 10 7 7 8 6 6 3 2 0 16 14 应用举例——关键路径 v2 v1 v3 v4 v5 v8 v6 v7 v9 a1=6 a4=1 a7=9 a10=2 a11=4 a8=7 a9=4 a5=1 a6=2 a3=5 a2=4 a2 a7 a6 a5 a4 a1 a3 a9 a8 a10 a11 v2 v7 v6 v5 v4 v1 v3 v9 v8 vl[k] 18 14 16 10 7 8 6 6 0 l[i]=vl[j]-lenvk, vj a2 a7 a6 a5 a4 a1 a3 a9 a8 e[i] l[i] 0 0 0 6 4 5 7 7 7 10 7 7 8 6 6 3 2 0 a10 a11 16 14 16 14 应用举例——关键路径 v2 v1 v3 v4 v5 v8 v6 v7 v9 a1=6 a4=1 a7=9 a10=2 a11=4 a8=7 a9=4 a5=1 a6=2 a3=5 a2=4 关键活动：l[i]=e[i]的活动 b a c d 7 6 2 f e 8 1 4 4 3 4 7 2 3 5 6 3 2 1 u0 g 课堂练习：求u0到其他各顶点的最短路径。 应用举例——关键路径 l(g) l(f) l(e) l(d) l(c) l(b) l(a) T S 7 1 2 ∞ ∞ 4 8 abcdefg u0 1 7 2 4 ∞ 4 8 abcdeg u0 f 2 7 3 ∞ 4 8 abcdg u0 fe 3 6 9 4 8 abcg u0 fed 4 6 9 6 acg u0 fedb 5 6 9 cg u0 fedba 6 9 c u0 fedbag 7 u0 fedbagc 8 应用举例——关键路径 Floyd算法 应用举例——最短路径 a c b 3 4 6 11 2 第3次迭代 dist2 = 0 4 6 5 0 2 3 7 0 path2 = ab abc bca bc ca cab dist1 = 0 4 6 6 0 2 3 7 0 path1 = ab abc ba bc ca cab 图的存储结构：带权的邻接矩阵存储结构 数组dist[n][n]：存放在迭代过程中求得的最短路径长度。迭代公式： 数组path[n][n]：存放从vi到vj的最短路径，初始为path[i][j]=vivj。 设计数据结构 dist-1[i][j]=arc[i][j] dist k[i][j]=min{distk-1[i][j], distk-1[i][k]+distk-1[k][j]} 0≤k ≤n-1 应用举例——最短路径 void Floyd(MGraph G) { for (i=0; iG.vertexNum; i++) ???? for (j=0; jG.vertexNum; j++) ???? { dist[i][j]=G.arc[i][j]; ?????? if (dist[i][j]!=∞) path[i][j]=G.vertex[i]+G.vertex[j]; ??????? else path[i][j]=; } 应用举例——最短路径 Floyd算法——C++描述 for (k=0; kG.vertexNum; k++) ????????for (i=0; iG.vertexNum; i++) ???????? for (j=0; jG.vertexNum; j++) ???????? if (dist[i][k]+dist[k][j]dist[i][j]) { ???????? dist[i][j]=dist[i][k]+dist[k][j]; ???????? path[i][j]=path[i][k]+path[k][j]; } } 应用举例——最短路径 Floyd算法——C++描述 AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。 应用