[理学]数据结构-第七章 图.ppt

7.1 图的基本概念 网的邻接表 7.4 图的连通性问题 7.6 最短路径 作业 7.1 已知如图所示的有向图，请给出该图的 （1）每个顶点的入/出度； （2）邻接矩阵 （3）邻接表 （4）逆邻接表 （5）强连同分量 7.2 含n个顶点的无向完全图，其边数为_____；n个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 7.3 若某图共有5个节点v0—v4，它的邻接矩阵如下,画出该图，该图是无向图还是有向图，给出各个顶点的入/出度 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 ?有关数据的存储结构 有向连通网络: G 采用带权邻接矩阵G.arcs[ ][ ]存储 ?具体步骤： （1）初始U={v0}, 用辅助数组 dist[0..N-1] vi ( i ? U )，vi 所对应的数组分量dist[i]的值为最短距离 vj (j ? V - U )，vj 所对应的数组分量dist[j]的值为Wvj，而Wvj为从v0出发，考虑途经已确定为终点的顶点，到达vj (i? V - U )的最短路径。 初始时: 对j ? V - U ，有dist[j] = G.arcs[v][j]; 而对U={v}, 则有dist[v]= G.arcs[v][v] ?迪杰斯特拉算法涉及的数据和操作： （2）扫描dist[ ]数组 找出未确定最短距离顶点中最小的dist[j]（j ? V - U ) 即从v0出发到vj（j ? V - U )的路径是最短的 （3）vj并入U （4）调整dist[k] (k ? V - U ) 考虑 从v0出发，途经新取得的vj到达vk是否更短。 比较： 若dist[j]+G.arcs[j][k]disk[k] 则dist[k]= disk[j]+ G.arcs[j][k] （5）重复（2）（3）（4）。共 n-1次。 求解步骤 dist[1] 路径终点1 dist[2] 路径终点2 dist[3] 路径终点3 dist[4] 路径终点4 dist[5] 路径终点5 最短路径 的终点 U：{V0} 辅助数组 max 100 （V0,V5） 10 （V0,V2） max 30 （v0,v4） V2 {V0,V2} i=1 max 10 （V0,V2） 60 （V0,V2,V3） 30 （V0，V4） V4 {V0,V2,V4} i=2 100 （V0,V5） 100 60 10 10 5 30 50 20 V5 V4 V0 V1 V2 V3 60 （V0,v4,v3,V5） 50 （V0,V4,v3） max 10 （V0,V2） 求解步骤 dist[1] 路径终点1 dist[2] 路径终点2 dist[3] 路径终点3 dist[4] 路径终点4 dist[5] 路径终点5 最短路径 的终点 U：{V} 辅助数组 10 （V0,v2） 50 (V0,v4,v3） 30 （V0,V4） max V3 {V0,V2,V4,V3} i=3 90 （V0,V4,v5） 30 （V0,V4） 50 （V0,V4,v3） 10 （V0,V2） max V5 {V0,V2,V4,V3,V5} i=4 60 （V0,v4,v3,V5） i=5 30 （V0,V4） 100 60 10 10 5 30 50 20 V5 V4 V0 V1 V2 V3 迪杰斯特拉算法的求解过程 迪杰斯特拉算法实现时的几个细节： (1)如何记录最短路径 D[j](j=0..G.vexnum-1): v0顶点到j顶点的目前求得的最短距离 对于j=v0: D[j]=0 初始时：v0到v有边或弧，D[j]=G.arcs[v0][j] 否则为无穷大的数值 (2)一个顶点是否已经确定了最短路径的标志 final[j](j=0..G.vexnum-1): TRUE:已经确定最短距离 FALSE:未确定最短距离 (3)最短路径上经由的顶点 P[j](j=0..G.vexnum-1):每个最短路径上的顶点集合 P[j][i](i=0..