数据结构（Python Java）（微课版） 课件 6.3 图的应用

数据结构与算法设计拓扑排序问题关键路径问题最短路径问题6.3图的应用最小生成树连通无向图中，如果从顶点v到顶点v'有路径，则称v和v'是连通的连通图如果图中任意两个顶点都是连通的，则是连通图连通分量无向图的极大连通子图连通图只有一个连通分量，即其自身非连通的无向图有多个连通分量最小生成树15732461573246强连通图有向图中，如果每一对顶点vi,vj∈V(vi!=vj)，从vi到vj和从vj到vi都存在路径，则称G是强连通图强连通分量有向图的极大强连通子图称作强连通分量强连通图的强连通分量是其自身非强连通的有向图可能有多个强连通分量最小生成树123245136生成树连通最小生成树是一个极小连通子图它含有图中全部顶点，但只有足以构成一棵树的n-1条边最小生成树生成树一个图可以有许多棵不同的生成树生成树具有以下共同特点：顶点个数与图的顶点个数相同是图的极小连通子图一个有n个顶点的连通最小生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树最小生成树设G=(V，E)是一个连通图则从图中任一顶点出发，遍历图G时，得到一个边集T(G)，T(G)与图中所有顶点一起构成图G的极小连通子图，它是连通图的一棵生成树。由DFS得到的是深度优先生成树由BFS得到的为广度优先生成树连通无向最小生成树V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树这些连通分量的生成树组成非连通图的生成森林非连通最小生成树ABLMCFDEGHKIJABLMCFJDEGHKI最小生成树不是唯一的从不同的顶点出发，能得到不同的生成树连通网络G=(V,E)各边带权生成树各边带权生成树的权生成树各边权值的和最小生成树权值最小的生成树最小生成树1654327131791812752410最小生成树问题提出在n个城市间建立通信网络顶点—表示城市权—城市间建立通信线路所需花费代价希望找到一条路径，使建立该通信网所需花费的总代价最小路径上各边权值的和最小问题分析n个城市间，最多可设置n(n-1)/2条线路n个城市间建立通信网，只需n-1条线路如何在可能的线路中选择n-1条边，把所有城市连起来，且总耗费(各边权值之和)最小找图中的最小生成树贪心（Prim）在对问题求解时，总是做出在当前看来是最好的选择算法得到的是在某种意义上的局部最优解贪心算法不是对所有问题都能得到整体最优解，但是在求最小生成树问题上适用贪心算法克鲁斯卡尔（Kruskal）算法寻找每一步当前情况下的最小路径不能形成回路无环图（DAG）一个无环（回路）的有向图叫做有向无环图AOV网顶点表示活动的网顶点表示活动弧表示活动间的先后关系AOV网中不允许有回路拓扑排序问题拓扑排序问题提出问题提出如果现在只有一名工人做整个工程，每次只能做一项活动，他应怎样安排所做事情的前后顺序，才能顺利完成此项工程。拓扑排序拓扑排序的方法从有向图中任选一个入度为0的顶点，并访问对所有以它为尾的弧，弧头顶点的入度减1删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已访问，或当图中不存在度为0的顶点为止不存在度为0的顶点:存在环拓扑排序举例V1：材料进场 V2：阀门试压 V3：预埋预留 V4：设备安装V5：管道预制 V6：支吊架安装 V7：单机试运转 V8：管道安装V9：试压、闭水 V10：卫生器具安装 V11：油漆防腐V12：冲洗消毒 V13：验收拓扑排序举例拓扑排序举例拓扑排序举例拓扑排序举例拓扑排序举例拓扑排序拓扑序列：V1→V2→V3→V4→V5→V6→V7→V8→V9→V10→V11→V12→V13或：V1→V2→V5→V3→V6→V8→V9→V11→V10→V12→V4→V7→V13AOV网的拓扑序列不是唯一的关键路径问题987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4用有向图表示工程计划，顶点表示事件，弧表示活动每个顶点表示在它之前的活动已完成，在它之后的活动可以开始问题描述一个工程有11项活动，9个事件V1表示工程开始，V9表示工程结束完成整项工程至少需要多少时间？哪些活动是影响工程进度的关键？源点和汇点正常情况(无环)下，网中只有一个入度为零的点,称为源点一个出度为零的点,称为汇点关键路径完成整个工程的最短时间是从源点到汇点的最长路径的长度(路径长度等于路径上各边的权之和)这条具有最大长度的路径称为关键路径关键路径问题的相关概念关键路径问题的相关概念ee(i)：表示事件Vi的最早发生时间le(i)：表示事件Vi的最迟发生时间e(k)：活动ak=<vi，vj>的最早开始时间l(k)：活动ak=<vi，vj>的最迟开始时间l(k)-e(k)：完成活动ak的时间余量关键活动：关键路径上的活动求关键路径步骤求ee(i)求le(j)求e(k)求l(k)计算l(k)-e(k)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4顶点eele0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动ell-e

00002266046258377077071031616014140033若:l(i)-e(i)=0，则ai是关键活动V1V2V3V4V5V6V7V8V9用带权的有向图表示一个交通运输网，图中：顶点：表示城市边：表示城市间的交通联系权：表示此线路的长度或沿此线路运输所花的时间或费用等问题提出：从某顶点出发，沿图的边到达另一顶点所经过的路径中，求各边上权值之和最小的一条路径（最短路径）最短路径问题迪杰斯特拉(Dijkstra)算法每次对所有可见点的路径长度进行排序后，选择一条最短的路径，这条路径就是对应顶点到源点的最短路径。以对应点为中继，优化它的邻接点到源点的路径。求单源最短路径弗洛伊德(Floy