[工学]实用数据结构基础第三版课程PPT第8章 图.ppt

预习题 1.什么叫深度优先有哪些信誉好的足球投注网站遍历？ 2.什么叫广度优先有哪些信誉好的足球投注网站遍历？ 练习题 解：（1）G的邻接表： 预习题 1.什么叫连通网的最小生成树？ 2.Prim算法和Kruskal算法的时间复杂度各是多少？它们适用于何种情况？ 3.拓扑排序定义是什么？拓扑排序是意义是什么？ 预习题 1、查找表是一种基本数据结构类型吗？ 2、什么叫静态查找表和动态查找表？ 3、什么是平均查找长度ASL？它和时间复杂度有什么不同？ 8-5 最短路径 最短路径问题是图的又一个比较典型的应用问题。例如，某一地区的一个交通网，给定了该网内的n个城市以及这些城市之间的相通公路的距离，问题是如何在城市A和城市B之间找一条最近的通路。如果将城市用顶点表示，城市间的公路用边表示，公路的长度则作为边的权值，那么，这个问题就可归结为在网中，求点A到点B的所有路径中，边的权值之和最短的那一条路径。这条路径就称为两点之间的最短路径，并称路径上的第一个顶点为源点（Sourse），最后一个顶点为终点（Destination）。在不带权的图中，最短路径是指两点之间经历的边数最少的路径。 例如在图８-23中，设V1为源点，则从V1出发的路径有（括号里为路径长度）： V1到V2的路径有1条：V1→V2(20) V1到V3的路径有2条：V1→V3(15),V1→V2→V3(55) V1到V4的路径有3条：V1→V2→V4(30),V1→V3→V4(45),V1→V2→V3→V4(85) V1到V5的路径有2条：V1→V2→V3→V5(65),V1→V3→V5(25) 选出V1到其它各顶点的最短路径，并按路径长度递增顺序排列如下： V1→V3(15)，V1→V2(20)，V1→V3→V5(25)，V1→V2→V4(30)。 图８-23 V1 出发的路径 V1 V5 V2 V4 V3 20 10 35 10 15 30 从上面的序列中，可以看出一个规律：按路径长度递增顺序生成从源点到其它各顶点的最短路径时，当前正生成的最短路径上除终点外，其它顶点的最短路径已经生成。迪杰斯特拉算法正是根据此规律得到的。 迪杰斯特拉（Dijkstra）算法的基本思想：设置两个顶点集S和T，S中存放已确定最短路径的顶点，T中存放待确定最短路径的顶点。初始时S中仅有一个源点，T中含除源点外其余顶点，此时各顶点的当前最短长度为源点到该顶点的弧上的权值。接着选取T中当前最短路径长度最小的一个顶点v加入S，然后修改T中剩余顶点的当前最短路径长度，修改原则是：当v的最短路径长度与v到T中顶点之间的权值之和小于该顶点的当前最短路径长度时，用前者替换后者。重复以上过程，直到S中包含所有顶点为止，其过程如图8－２4。 图８-24 用迪杰斯特拉算法求有向图的最短路径过程 V1 V5 V2 V4 V3 20 10 35 10 15 30 V1 V5 V2 V4 V3 20 15 V1 V5 V2 V4 V3 20 10 15 30 V1 V5 V2 V4 V3 20 10 15 30 V1 V5 V2 V4 V3 20 10 15 30 10 V0 V1 V2 V3 V4 V5 5 10 50 20 30 60 10 100 ∞ 0 路径P 0, ∞ 0 长度D S 5 4 3 2 1 0 i 10 02 30 100 04 05 2, 60 023 4, 50 043 90 045 如图8-25所示的有向网中，从顶点A到其余各顶点的最短路径如表8-1所示。 图8-25 有向网 表8-1 顶点A到其它顶点的最短路径 以图8-25所示的有向网为实例，迪杰斯特拉算法求解该网中从源点A到其余各顶点最短路径的过程如图8-26所示。 图8-26 迪杰斯特拉算法的求解过程 迪杰斯特拉算法求最短路径的过程描述如下： #define INFINITY 99999 #define MAXLEN 20 typedef bool PathMatrix[MAXLEN][MAXLEN]; typedef int ShortPathTable[MAXLEN]; void ShortestPath(MGraph G, int v0, PathMatrix P, ShortPathTable D) { for(v=0; vG.VexNum; v++) { final[v]=False; // 初始化S集合为空 for(w=0; wG.VexNum; w++) // 初始化最短路径矩阵P P[v][w]=False; // 没有存储任何最短路径，