1、第第7章章 图图学习关键点学习关键点:了解图定义和与图相关术语。了解图定义和与图相关术语。了解图是一个表示复杂非线性关系数据结构。了解图是一个表示复杂非线性关系数据结构。掌握图邻接矩阵表示及其实现方法。掌握图邻接矩阵表示及其实现方法。掌握图邻接表表示及其实现方法。掌握图邻接表表示及其实现方法。了解图紧缩邻接表表示方法。了解图紧缩邻接表表示方法。掌握图广度优先搜索方法。掌握图广度优先搜索方法。掌握图深度优先搜索方法。掌握图深度优先搜索方法。掌握单源最短路径问题掌握单源最短路径问题Dijkstra算法。算法。掌握有掌握有负权边单源最短路径源最短路径问题Bellman-Ford算法算法掌握全部顶点对
2、之间最短路径问题掌握全部顶点对之间最短路径问题Floyd算法。算法。掌握结构最小支撑树掌握结构最小支撑树Prim算法。算法。掌握结构最小支撑树掌握结构最小支撑树Kruskal算法。算法。了解图最大匹配问题增广路径算法。了解图最大匹配问题增广路径算法。2024/9/2911/84第第7章章 图图7.1 图定义和术语图定义和术语图图(Graph)图图G是由两个集合是由两个集合V(G)和和E(G)组成组成,记为记为G=(V,E)其中：其中：V(G)是顶点非空有限集是顶点非空有限集 E(G)是边有限集合，边是顶点无序对或有序对是边有限集合，边是顶点无序对或有序对有向图有向图图图G中每条边都是有方向中每
3、条边都是有方向 有向图有向图G是由两个集合是由两个集合V(G)和和E(G)组成组成 其中：其中：V(G)是顶点非空有限集是顶点非空有限集 E(G)是有向边（也称弧）有限集合，弧是顶点有序对，记为是有向边（也称弧）有限集合，弧是顶点有序对，记为，v,w是顶点，是顶点，v为弧尾，为弧尾，w为弧头为弧头无向图无向图图图G中每条边都是没有方向中每条边都是没有方向无向图无向图G是由两个集合是由两个集合V(G)和和E(G)组成组成 其中：其中：V(G)是顶点非空有限集是顶点非空有限集 E(G)是边有限集合，边是顶点无序对，记为是边有限集合，边是顶点无序对，记为 （v,w）或（）或（w,v)，而且（，而且（
4、v,w)=(w,v)2024/9/2922/842024/9/293例245136G1图G1中：V(G1)=1,2,3,4,5,6 E(G1)=,例157324G26图G2中：V(G2)=1,2,3,4,5,6,7 E(G2)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)3/84有向完备图n个顶点有向图最大边数是n(n-1)无向完备图n个顶点无向图最大边数是n(n-1)/2关联 P225权与图边或弧相关数叫网带权图叫子图假如图G(V,E)和图G(V,E),满足：VVEE 则称G为G子图顶点度无向图中，顶点度为与每个顶点相连边数有向图中，顶点度分成入度与出度
5、,假设一顶点v,入度：以顶点v为终点边数目，记为ID（v）出度：以顶点v为起点边数目，记为OD（v）路径路径是顶点序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1jn)2024/9/2944/84路径长度沿路径边数目或沿路径各边权值之和回路第一个顶点和最终一个顶点相同路径叫简单路径序列中顶点不重复出现路径叫简单回路除了第一个顶点和最终一个顶点外，其余顶点不重复出现回路叫连通从顶点V到顶点W有一条路径，则说V和W是连通连通图图中任意两个顶点都是连通叫连通分量非连通图每一个连通部分叫强连通图有向图中，假如对每一对Vi,VjV,ViVj,从Vi到Vj 和从Vj到 Vi都存在
6、路径，则称G是2024/9/2955/842024/9/296例213213有向完备图无向完备图356例245136图与子图例245136G1顶点2入度：1 出度：3顶点4入度：1 出度：0例157324G26顶点5度：3顶点2度：46/842024/9/297例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，17/842024/9/298连通图例2451
7、36强连通图356例非连通图连通分量例2451368/847.2 图表示法图表示法邻接矩阵表示顶点间相联关系矩阵定义：设G=(V,E)是有n1个顶点图，G邻接矩阵A是含有以下性质n阶方阵2024/9/299例G12413例15324G29/84特点：无向图邻接矩阵对称，可压缩存放；有n个顶点无向图需存放空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点有向图需存放空间为n无向图中顶点Vi度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi出度是A中第i行元素之和顶点Vi入度是A中第i列元素之和网络邻接矩阵可定义为：2024/9/291010/842024/9/2911例1452
8、37531864211/842024/9/2912基本思想基本思想：对图每个顶点建立一个单链表，对图每个顶点建立一个单链表，存放该顶点全部邻接顶点及其相关信息。每存放该顶点全部邻接顶点及其相关信息。每一个单链表设一个表头结点。一个单链表设一个表头结点。第第i个单链表表示依附于顶点个单链表表示依附于顶点Vi边边(对有对有向图是以顶点向图是以顶点Vi为头或尾弧为头或尾弧)。7.2.2 邻接链表法邻接链表法12/84邻接表实现：为图中每个顶点建立一个单链表，第i个单链表存放顶点Vi全部邻接顶点。2024/9/291313/84特点特点无向图中顶点无向图中顶点Vi度为第度为第i个单链表中结点数个单链表
9、中结点数有向图中有向图中顶点顶点Vi出度为第出度为第i个单链表中结点个数个单链表中结点个数顶点顶点Vi入度为整个单链表中邻接点域值是入度为整个单链表中邻接点域值是i结点结点个数个数逆邻接表：有向图中对每个结点建立以逆邻接表：有向图中对每个结点建立以Vi为终点边为终点边单链表单链表2024/9/2914求解麻烦！例 1 3 11342 2 414/84习题1、有如图所表示有向图，画出该图：(1)邻接矩阵；(2)邻接表。2024/9/291515/847.2.3 十字链表法十字链表法十字链表十字链表(Orthogonal List)是有向图另一个链式存放结是有向图另一个链式存放结构，是将有向图正邻
10、接表和逆邻接表结合起来得到一个构，是将有向图正邻接表和逆邻接表结合起来得到一个链表。链表。在这种结构中，每条弧弧头结点和弧尾结点都存放在这种结构中，每条弧弧头结点和弧尾结点都存放在链表中，在链表中，并将弧结点并将弧结点分别组织到分别组织到以弧尾结点为头以弧尾结点为头(顶点顶点)结点结点和和以弧头结点为头以弧头结点为头(顶点顶点)结点结点链链表中。表中。2024/9/291616/842024/9/2917弧结点弧结点tailvex headvex info hlink tlink顶点结点顶点结点Data firstin firstout图图7-12 十字链表结点结构十字链表结点结构17/84
11、data域：存放和顶点相关信息；域：存放和顶点相关信息；指针域指针域firstin：指向以该顶点为弧头第一条弧：指向以该顶点为弧头第一条弧所对应弧结点；所对应弧结点；指针域指针域firstout：指向以该顶点为弧尾第一条弧：指向以该顶点为弧尾第一条弧所对应弧结点；所对应弧结点；尾域尾域tailvex：指示弧尾顶点在图中位置；：指示弧尾顶点在图中位置；头域头域headvex：指示弧头顶点在图中位置；：指示弧头顶点在图中位置；指针域指针域hlink：指向弧头相同下一条弧；：指向弧头相同下一条弧；指针域指针域tlink：指向弧尾相同下一条弧；：指向弧尾相同下一条弧；Info域：指向该弧相关信息；域：
12、指向该弧相关信息；2024/9/291818/842024/9/2919V0V1V2V30 10 2 2 02 3 3 0 3 1 3 2 0213V0V1 V2V3图图7-13 有向图十字链表结构有向图十字链表结构19/847.2.4 邻接多重表邻接多重表 邻接多重表邻接多重表(Adjacency Multilist)是无向图另一是无向图另一个链式存放结构。个链式存放结构。邻接表是无向图一个有效存放结构，在无邻接表是无向图一个有效存放结构，在无向图邻接表中，一条边向图邻接表中，一条边(v,w)两个表结点分别初两个表结点分别初选在以选在以v和和w为头结点链表中，很轻易求得顶点为头结点链表中，很
13、轻易求得顶点和边信息，但在包括到边操作会带来不便。和边信息，但在包括到边操作会带来不便。邻接多重表结构和十字链表类似，邻接多重表结构和十字链表类似，每条边每条边用一个结点表示用一个结点表示；邻接多重表中顶点结点结构；邻接多重表中顶点结点结构与邻接表中完全相同，而表结点包含六个域如与邻接表中完全相同，而表结点包含六个域如图图7-14所表示。所表示。20/842024/9/2921data firstedge顶点结点顶点结点图图7-14 邻接多重表结点结构邻接多重表结点结构表结点表结点mark ivex jvex info ilink jlink21/84 Data域：存放和顶点相关信息；域：存放
14、和顶点相关信息；指针域指针域firstedge：指向依附于该顶点第一条边所：指向依附于该顶点第一条边所对应表结点；对应表结点；标志域标志域mark：用以标识该条边是否被访问过；：用以标识该条边是否被访问过；ivex和和jvex域：分别保留该边所依附两个顶点在域：分别保留该边所依附两个顶点在图中位置；图中位置；info域：保留该边相关信息；域：保留该边相关信息；指针域指针域ilink：指向下一条依附于顶点：指向下一条依附于顶点ivex边；边；指针域指针域jlink：指向下一条依附于顶点：指向下一条依附于顶点jvex边；边；22/84邻接多重表与邻接表区分邻接多重表与邻接表区分：后者同一条边用两个
15、表结点表示，而前者后者同一条边用两个表结点表示，而前者只用一个表结点表示只用一个表结点表示；除标志域外，邻接多重除标志域外，邻接多重表与邻接表表示信息是相同，所以，操作实现表与邻接表表示信息是相同，所以，操作实现也基本相同。也基本相同。图图7-15 无向图及其多重邻接链表无向图及其多重邻接链表v1v2v3v4v1v2v3v40123 0 1 0 2 2 1 2 3 0 323/847.3 图遍历深度优先遍历深度优先遍历(DFS)方法：从图某一顶点V0出发，访问此顶点；然后依次从V0未被访问邻接点出发，深度优先遍历图，直至图中全部和V0相通顶点都被访问到；若此时图中还有顶点未被访问，则另选图中一
16、个未被访问顶点作起点，重复上述过程，直至图中全部顶点都被访问为止（问题：什么时候会出现这种情况？）2024/9/2924类似于：树前序遍历！24/842024/9/2925V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V725/842024/9/2926V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V3 V7深度遍历：V1 V2 V4 V8 V5 V6 V3 V726/842024/9/2927V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V527
17、/842024/9/2928V1V2V4V5V3V7V6V8例深度遍历：V112341342vexdata firstarc 2 7 8 3adjvex next55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V3 V7 V6 V2 V5 V8 V428/842024/9/2929V1V2V4V5V3V7V6V8例12341342vexdata firstarc 2 7 8 3adjvex next55 6 4 8 2678678 7深度遍历：V1V3 V7 V6 V2 V4 V8 V529/842024/9/29301、已知一个图以下所表示已知一个图以下所表示,则从顶
18、点则从顶点a 出发按深度优先出发按深度优先搜索则能够得到一个顶点序列为搜索则能够得到一个顶点序列为_(A)a,b,e,d,f,c (B)a,c,f,e,b,d (C)a,e,b,c,f,d (D)a,e,d,f,b,c30/842024/9/29312、以下列图所表示带权有向图以下列图所表示带权有向图G,试回答试回答以下问题以下问题:给出从结点v1出发按深度优先搜索遍历G所得结点序列,并给出按广度优先搜索遍历G所得结点序列.31/842024/9/29327.3 图遍历广度优先搜索广度优先搜索(BFS)v方法：从图某一顶点V0出发，访问此顶点后，依次访问V0各个未曾访问过邻接顶点；然后分别从这
19、些邻接顶点出发，广度优先遍历图，直至图中全部已被访问顶点邻接点都被访问到；若此时图中还有顶点未被访问，则另选图中一个未被访问顶点作起点，重复上述过程，直至图中全部顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V8类似于：树层次遍历！32/847.4生成树生成树生成树生成树定义：全部顶点均由边连接在一起，但不存在回路图定义：全部顶点均由边连接在一起，但不存在回路图叫叫说明：说明：一个图能够有许多棵不一样生成树一个图能够有许多棵不一样生成树全部生成树含有以下共同特点：全部生成树含有以下共同特点：生成树顶点个数与图顶点个数相同生成树顶点个数与图
20、顶点个数相同生成树是图极小连通子图生成树是图极小连通子图一个有一个有n个顶点连通图生成树有个顶点连通图生成树有n-1条边条边生成树中任意两个顶点间路径是唯一生成树中任意两个顶点间路径是唯一在生成树中再加一条边必定形成回路在生成树中再加一条边必定形成回路含含n个顶点个顶点n-1条边图不一定是生成树条边图不一定是生成树2024/9/2933GHKI33/84u在对在对无向连通图无向连通图进行遍历时，遍历所得到连通分量包含了图中全部顶点进行遍历时，遍历所得到连通分量包含了图中全部顶点和和n1条边，它们组成了连通图一棵生成树。条边，它们组成了连通图一棵生成树。由由深度优先遍历深度优先遍历得到生成树称为
21、得到生成树称为深度优先生成树深度优先生成树；由由广度优先遍历广度优先遍历得到生成树称为得到生成树称为广度优先生成树广度优先生成树。u对于对于非连通图非连通图，则需要进行屡次遍历过程，每次从一个新顶点出发，则需要进行屡次遍历过程，每次从一个新顶点出发，而且每次得到顶点访问序列是各个连通分量中顶点集。而且每次得到顶点访问序列是各个连通分量中顶点集。34/842024/9/29353535/84最小生成树问题提出2024/9/2936要在n个城市间建立通信联络网，顶点表示城市权城市间建立通信线路所需花费代价希望找到一棵生成树，它每条边上权值之和（即建立该通信网所需花费总代价）最小最小代价生成树v问题
22、分析1654327131791812752410n个城市间，最多可设置n(n-1)/2条线路n个城市间建立通信网，只需n-1条线路问题转化为：怎样在可能线路中选择n-1条，能把 全部城市（顶点）均连起来，且总花费 （各边权值之和）最小36/84最小生成树性质用贪心算法设计策略能够设计出结构最小生成树有效算法。本节介绍结构最小生成树PrimPrim算法算法和KruskalKruskal算法算法都能够看作是应用贪心算法设计策略例子。尽管这2个算法做贪心选择方式不一样，它们都利用了下面最小生成树性质最小生成树性质：设G=(V,E)是连通带权图，U是V真子集。假如(u,v)E，且uU，vV-U，且在全
23、部这么边中，(u,v)权cuv最小，那么一定存在G一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MSTMST性性质质。2024/9/293737/84结构最小生成树方法方法一：Prim算法算法思想：设G=(V,E)是连通网，T是N上最小生成树中边集合初始令U=u0,(u0V),T=在全部uU,vV-U边(u,v)E中，找一条代价最小边(u0,v0)将(u0,v0)并入集合T，同时v0并入U重复上述操作直至U=V为止，则T=(V,T)为N最小生成树2024/9/293838/842024/9/2939例165432651356642513116314164314211643214
24、251654321425339/84方法二：Kruskal算法算法思想：设G=(V,E)，令最小生成树初始状态为只有n个顶点而无边非连通图T=(V,)，每个顶点自成一个连通分量在E中选取代价最小边，若该边依附顶点落在T中不一样连通分量上，则将此边加入到T中；不然，舍去此边，选取下一条代价最小边依这类推，直至T中全部顶点都在同一连通分量上为止2024/9/2940例16543265135664251654321234540/842024/9/294141/842024/9/2942v算法描述：uPrim算法与Kruskal算法比较 从算法时间复杂性看:当e=(n2)时，Kruskal算法比Pri
25、m算法差，但当e=o(n2)时，Kruskal算法却比Prim算法好得多。u算法分析：设输入连通赋权图有e条边，则将这些边依其权值组成优先队列需要O(e)时间；while循环中，DeleteMin运算需要O(loge)时间，所以关于优先队列所作运算时间为O(eloge)。实现UnionFind所需时间为O(eloge)。Kruskal算法所需计算时间是O(eloge)。42/847.6 有向无环图及其应用有向无环图及其应用 有向无环图有向无环图：是图中没有回路：是图中没有回路(环环)有向图。是有向图。是一类含有代表性图，主要用于研究工程项目标工一类含有代表性图，主要用于研究工程项目标工序问题序
26、问题、工程时间进度问题等。工程时间进度问题等。一个一个工程工程都可分为若干个称为都可分为若干个称为活动活动子工程子工程(或或工序工序)，各个子工程受到一定条件约束各个子工程受到一定条件约束：某个子工：某个子工程必须开始于另一个子工程完成之后；整个工程程必须开始于另一个子工程完成之后；整个工程有一个开始点有一个开始点(起点起点)和一个终点。人们关心：和一个终点。人们关心：工程能否顺利完成工程能否顺利完成?影响工程关键活动是什么影响工程关键活动是什么?估算整个工程完成所必须最短时间是多少估算整个工程完成所必须最短时间是多少?43/84 对工程活动加以抽象：图中顶点表示活动，对工程活动加以抽象：图中
27、顶点表示活动，有向边表示活动之间优先关系，这么有向图称有向边表示活动之间优先关系，这么有向图称为为顶点表示活动网顶点表示活动网(Activity On Vertex Network，AOV网网)。44/84 7.6.1 拓扑排序拓扑排序问题提出：学生选修课程问题顶点表示课程有向弧表示先决条件，若课程i是课程j先决条件，则图中有弧学生应按怎样次序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序 2024/9/294545/84拓扑排序拓扑排序把AOV网络中各顶点按照它们相互之间优先关系排列成一个线性序列过程叫检测AOV网中是否存在环方法：对有向图结构其顶点拓扑有序序列，若网中全部顶点都在它拓扑有
28、序序列中，则该AOV网必定不存在环 拓扑排序方法拓扑排序方法在有向图中选一个没有前驱顶点且输出之从图中删除该顶点和全部以它为尾弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱顶点为止2024/9/294646/842024/9/2947例课程代号 课程名称 先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C1247/842024/9/
29、2948C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一个AOV网拓扑序列不是唯一48/842024/9/2949C1C2C3C4C5C6C7C8C9C10C11C1249/842024/9/2950C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2（2）50/842024/9/2951C4C5C6C7C8C9C10C11C12拓扑序列
30、：C1-C2-C3（3）C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4（4）51/842024/9/2952C6C8C10C11C12拓扑序列：C1-C2-C3-C4-C5-C7-C9C6C8C11C12拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10（8）C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4-C5（5）C6C8C9C10C11C12拓扑序列：C1-C2-C3-C4-C5-C7（6）52/842024/9/2953C6C8C12拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11（9）C8C12拓扑序列：C1-C
31、2-C3-C4-C5-C7-C9 -C10-C11-C6（10）C8拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12（11）拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12-C8（12）53/842024/9/29547.6.2 关键路径关键路径1关键路径定义关键路径定义 2关键路径基本术语关键路径基本术语 3关键路径算法关键路径算法 54/842024/9/29551关键路径定义关键路径定义 用顶点表示事件，用弧表示活动，用权值表示活用顶点表示事件，用弧表示活动，用权值表示活动所需要时间，这种结构有向无环图称为边表示动所需要
32、时间，这种结构有向无环图称为边表示活动网，简称活动网，简称AOE网。网。在在AOE网中存在唯一、入度为网中存在唯一、入度为0顶点，称为顶点，称为源点源点。存在唯一、出度为存在唯一、出度为0顶点，称为顶点，称为汇点汇点。从源点到汇点最长路径长度即为完成整个工程任务所需时间，该从源点到汇点最长路径长度即为完成整个工程任务所需时间，该长度最长路径称为长度最长路径称为关键路径关键路径，关键路径上活动称为，关键路径上活动称为关键活动关键活动。55/842024/9/2956v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8
33、=4a11=2图图7-24 一个一个AOE网网56/84与与AOE相关研究问题相关研究问题 完成整个工程最少需要多少时间完成整个工程最少需要多少时间?哪些活动是影响工程进度哪些活动是影响工程进度(费用费用)关键关键?2024/9/295757/84工程完成最短时间工程完成最短时间：从起点到终点最长路径长度：从起点到终点最长路径长度(路径上路径上各活动连续时间之和各活动连续时间之和)。长度最长路径称为长度最长路径称为关键路径关键路径，关键路径上活动称为关键路径上活动称为关键活动关键活动。关键活动是影响整个工关键活动是影响整个工程关键程关键。设设v0是起点，从是起点，从v0到到vi最长路径长度称为
34、事件最长路径长度称为事件vi最早最早发生时间，即是以发生时间，即是以vi为尾全部活动最早发生时间。为尾全部活动最早发生时间。2024/9/295858/842024/9/29592关键路径基本术语关键路径基本术语 事件事件Vi最早发生时间最早发生时间Ve(i)：从源点：从源点V0到顶点到顶点Vi最长路径长度。最长路径长度。事件事件Vi最晚发生时间最晚发生时间Vl(i)：在确保汇点按其最早发生时间发生前提下，：在确保汇点按其最早发生时间发生前提下，事件事件Vi最晚发生时间。最晚发生时间。活动活动ai最早开始时间最早开始时间e(i)：假如活动：假如活动ai对应弧为对应弧为，则，则e(i)为从源点为
35、从源点到顶点到顶点Vj最长路径长度，即最长路径长度，即e(i)Ve(j)。活动活动ai最晚开始时间最晚开始时间l(i)：假如活动：假如活动ai对应弧为对应弧为，则，则l(i)为在确保为在确保事件事件Vk最晚发生时间最晚发生时间vl(k)前提下（或者在确保不推迟整个工期前提下），前提下（或者在确保不推迟整个工期前提下），活动活动ai最晚开始时间，故有最晚开始时间，故有l(i)Vl(k)dut()。活动活动ai松弛时间松弛时间（时间余量）：活动（时间余量）：活动ai最晚开始时间与最早开始时间之最晚开始时间与最早开始时间之差。差。关键活动关键活动：松弛时间（时间余量）为：松弛时间（时间余量）为0活动
36、。活动。59/84 算法思想算法思想 利用拓扑排序求出利用拓扑排序求出AOE网一个拓扑序列网一个拓扑序列；从拓扑排序序列第一个顶点从拓扑排序序列第一个顶点(源点源点)开始，按拓扑次序依次计开始，按拓扑次序依次计算每个事件最早发生时间算每个事件最早发生时间ve(i)；从拓扑排序序列最终一个顶点从拓扑排序序列最终一个顶点(汇点汇点)开始，按逆拓扑次序依开始，按逆拓扑次序依次计算每个事件最晚发生时间次计算每个事件最晚发生时间vl(i)；2024/9/296060/84 对于图对于图7-24AOE网，处理过程以下：网，处理过程以下：拓扑排序序列是：拓扑排序序列是：(v0,v1,v2,v3,v4,v5,
37、v6,v7,v8)依据计算依据计算ve(i)公式公式(7-2)和计算和计算vl(i)公式公式(7-3)，计算各个事件，计算各个事件ve(i)和和vl(i)值，如表值，如表7-2所表示。所表示。依据关键路径定义，知该依据关键路径定义，知该AOE网关键路径是：网关键路径是：(v0,v2,v4,v7,v8)和和(v0,v2,v5,v7,v8)。关键路径活动是：关键路径活动是：，。2024/9/296161/842024/9/2962顶点顶点v0v1v2v3v4v5v6v7v8ve(i)031012 22 17 20 2833vl(i)091023 22 17 31 2833表表7-2 图图7-24v
38、e(i)和和vl(i)值值62/847.7 最短路径最短路径 若用带权图表示交通网若用带权图表示交通网，图中顶点表示地，图中顶点表示地点，边代表两地之间有直接道路，边上权值表点，边代表两地之间有直接道路，边上权值表示旅程示旅程(或所花费用或时间或所花费用或时间)。从一个地方到另。从一个地方到另一个地方路径长度表示该路径上各边权值之和。一个地方路径长度表示该路径上各边权值之和。问题问题：两地之间是否有通路两地之间是否有通路?在有多条通路情况下在有多条通路情况下，哪条最短，哪条最短?63/84 考虑到交通网有向性，直接讨论是带权有向图最短路径考虑到交通网有向性，直接讨论是带权有向图最短路径问题，但
39、处理问题算法也适合用于无向图问题，但处理问题算法也适合用于无向图。将一个路径起始顶点称为源点将一个路径起始顶点称为源点，最终一个，最终一个顶点称为顶点称为终点。终点。2024/9/296464/847.7.1 单源点最短路径单源点最短路径 对于给定有向图对于给定有向图G=(V，E)及单个源点及单个源点Vs，求求Vs到到G其余各顶点最短路径。其余各顶点最短路径。针对单源点最短路径问题针对单源点最短路径问题，Dijkstra提出了提出了一个按路径长度递增次序产生最短路径算法，一个按路径长度递增次序产生最短路径算法，即即迪杰斯特拉迪杰斯特拉(Dijkstra)算法。算法。65/841 基本思想基本思
40、想 从图从图给定给定源点到其它各个顶点之间客观上应存在一源点到其它各个顶点之间客观上应存在一条最短路径，在这组最短路径中，按其长度递增次序，条最短路径，在这组最短路径中，按其长度递增次序，依次求出到不一样顶点最短路径和路径长度。依次求出到不一样顶点最短路径和路径长度。即按长度递增次序生成各顶点最短路径，即先求出即按长度递增次序生成各顶点最短路径，即先求出长度最小一条最短路径，然后求出长度第二小最短路径，长度最小一条最短路径，然后求出长度第二小最短路径，依这类推，直到求出长度最长最短路径。依这类推，直到求出长度最长最短路径。2024/9/296666/842 算法思想说明算法思想说明 设设给定给
41、定源点为源点为Vs，S为已求得最短路径终为已求得最短路径终点集，开始时令点集，开始时令S=Vs。当求得第一条最短路。当求得第一条最短路径径(Vs，Vi)后后，S为为Vs，Vi。依据以下结论可。依据以下结论可求下一条最短路径。求下一条最短路径。设下一条最短路径终点为设下一条最短路径终点为Vj，则，则Vj只有：只有：源点到终点有直接弧源点到终点有直接弧；从从Vs 出发到出发到Vj 这条最短路径所经过全部中间这条最短路径所经过全部中间顶点顶点必定在必定在S中。即只有这条最短路径最终一条弧才是从中。即只有这条最短路径最终一条弧才是从S内某个顶点连内某个顶点连接到接到S外顶点外顶点Vj。67/84 若定
42、义一个数组若定义一个数组distn，其每个，其每个disti分量分量保留从保留从Vs 出发中间只经过集合出发中间只经过集合S中中顶点而顶点而抵达抵达Vi全部路径中长度最小路径长度值全部路径中长度最小路径长度值，则，则下一条最下一条最短路径终点短路径终点Vj必定是不在必定是不在S中且值最小顶点中且值最小顶点，即，即：disti=Min distk|VkV-S 利用上述公式就能够依次找出下一条利用上述公式就能够依次找出下一条最短路最短路径。径。68/843 算法步骤算法步骤 令令S=Vs，用带权邻接矩阵表示有向图，对图中每个顶点，用带权邻接矩阵表示有向图，对图中每个顶点Vi按以下标准置初值：按以下
43、标准置初值：2024/9/2969Wsi is且且 E，wsi为弧上权值为弧上权值 is且且不属于不属于Edisti=0 0 i=s69/84 选择一个顶点选择一个顶点Vj，使得，使得：distj=Min distk|VkV-S Vj就是求得下一条最短路径终点就是求得下一条最短路径终点，将将Vj 并入到并入到S中，中，即即S=SVj 。对对V-S中每个顶点中每个顶点Vk，修改修改distk，方法是，方法是：若若distj+Wjkdistk，则修改为，则修改为：distk=distj+Wjk(VkV-S)重复重复，直到，直到S=V为止为止。70/8401234520306065152010804
44、03570图图7-25 带权有向图及其带权有向图及其邻接邻接矩阵矩阵 20 60 10 65 30 70 40 35 20 15 80 71/84 顶点顶点步骤步骤12345S初态初态Distpre200600010065001Distpre20060001003040,42Distpre2005019011003040,4,13Distpre2004559011003040,4,1,54Distpre2004558521003040,4,1,5,25Distpre2004558521003040,4,1,5,2,3表表7-3 求最短路径时数组求最短路径时数组dist和和pre各分量改变情况各
45、分量改变情况72/847.7.2 每一对顶点间最短路径每一对顶点间最短路径 用用Dijkstra算法也能够求得算法也能够求得有向图有向图G=(V，E)中每一对顶点间最短路径。方法是中每一对顶点间最短路径。方法是：每次：每次以一个不一样顶点为源点重复以一个不一样顶点为源点重复Dijkstra算法便算法便可求得可求得每一对顶点间最短路径每一对顶点间最短路径，时间复杂度，时间复杂度是是O(n3)。弗罗伊德弗罗伊德(Floyd)提出了另一个算法提出了另一个算法，其，其时间复杂度仍是时间复杂度仍是O(n3)，但算法形式更为简但算法形式更为简明，步骤更为简单，数据结构依然是基于图明，步骤更为简单，数据结构
46、依然是基于图邻接邻接矩阵矩阵。73/841 算法思想算法思想 设顶点集设顶点集S(初值为空初值为空)，用数组，用数组A每个元素每个元素Aij保留从保留从Vi只经过只经过S中顶点抵达中顶点抵达Vj最短路径最短路径长度，其思想是：长度，其思想是：初始时令初始时令S=，Aij赋赋初值方式是初值方式是：Wij ij且且 E，wij为弧上权值为弧上权值 ij且且不属于不属于EAij=0 0 i=j时时74/842024/9/2975 将图中一个顶点将图中一个顶点Vk 加入到加入到S中中，修改，修改Aij值值，修改方法是，修改方法是：Aij=MinAij,(Aik+Akj)原因原因：从从Vj只经过只经过S
47、中顶点中顶点(Vk)抵达抵达Vj路径长度可能比原路径长度可能比原来不经过来不经过Vk路径更短。路径更短。重复重复，直到，直到G全部顶点都加入到全部顶点都加入到S中为中为止止。75/84表表7-4给出了利用给出了利用Floyd算法求算法求图图7-26带权带权有向图任意一对顶点间有向图任意一对顶点间最短路径过程。最短路径过程。图图7-26 带权有向图及其带权有向图及其邻接邻接矩阵矩阵 0 2 8 0 4 5 0V1482V2V0576/84表表7-4 用用Floyd算法求任意一对顶点间算法求任意一对顶点间最短路径最短路径 0 2 8 0 45 0 0 2 8 0 4 5 7 0 0 2 6 0 4
48、 5 7 0 0 2 6 9 0 4 5 7 0A-1 -1 -1-1 -1 -1-1 -1 -1-1 -1 -1-1 -1 -1-1 0 -1-1 -1 1-1 -1 -1-1 0 -1-1 -1 1 2 -1 -1-1 0 -1PathS 0 0,1 0,1,2 步骤步骤初态初态k=0K=1K=277/84 依据上述过程中依据上述过程中Pathij数组数组，得出：得出：V0到到V1：最短路径是最短路径是 0,1 ，路径长度是，路径长度是2；V0到到V2：最短路径是最短路径是 0,1,2 ，路径长度是，路径长度是6；V1到到V0：最短路径是最短路径是 1,2,0 ，路径长度是，路径长度是9；
49、V1到到V2：最短路径是最短路径是 1,2 ，路径长度是，路径长度是4；V2到到V0：最短路径是最短路径是 2,0 ，路径长度是，路径长度是5；V2到到V1：最短路径是最短路径是 2,0,1 ，路径长度是，路径长度是7；78/84习习 题题 七七 分析并回答以下问题：分析并回答以下问题：图中顶点度之和与边数之和关系图中顶点度之和与边数之和关系?有向图中顶点入度之和与出度之和关系有向图中顶点入度之和与出度之和关系?含有含有n个顶点无向图，最少应有多少条边才能确保是一个连个顶点无向图，最少应有多少条边才能确保是一个连通图通图?若采取邻接矩阵表示，则该矩阵大小是多少若采取邻接矩阵表示，则该矩阵大小是
50、多少?含有含有n个顶点有向图，最少应有多少条弧才能确保是强连通个顶点有向图，最少应有多少条弧才能确保是强连通图图?为何为何?设一有向图设一有向图G=(V,E)，其中，其中V=a,b,c,d,e，E=,79/84 请画出该有向图，并求各顶点入度和出度。请画出该有向图，并求各顶点入度和出度。分别画出有向图正分别画出有向图正邻接链表和逆邻接链表邻接链表和逆邻接链表。对图对图7-27所表示带权无向图。所表示带权无向图。写出对应邻接矩阵表示。写出对应邻接矩阵表示。写出对应边表表示。写出对应边表表示。求出各顶点度。求出各顶点度。已知有向图逆邻接链表如图已知有向图逆邻接链表如图7-28所表示。所表示。画出该
