15.第15节课第7章图

罗泽兵 · 发表于 2024-4-15 09:19:32

那么，我们如何取得它的这样一个拓扑序列呢？那么，第一步呢？是从有效途中选择一个没有前驱的顶点，并且输出。第二步呢，是从有效途中删去此顶点，以及呢，所有以它为尾的弧那么重复，这样一个操作，直到图为空或者图中不为空，但是找不到没有前序的顶点为止，那么我们就。完成了这样一个操作的这样一个步骤就进行了这样一个操进行这样一个实验使用的操作，

那么接下来我们看一下关键路径。那么，什么是那么那么这样一个含义是什么呢？它的这样一个，它这样一个。采用的这样一个用使用的方方用途是什么呢？它的这样一个作用效用途是什么呢？关键路径，比如说假设以有向图表示，一个施工流图图上的全值。表示该完成完成该项子工程需要的时间，那么我们来看一下哪些子工程项是关键路工程。就是说哪些子功能下来将影响整个工程的工期的完成时，完成期限，那么这是说它的这样一个。

用用使用的方方式是什么？整个工程的完成时间呢，是从有效图的原点到我们的会议点。的最长路径就是工程的完成时间，关键活动呢，是指该活的全职将增加，将使有效图上的最长路径。强度增加。那么，我们怎么求关键活动呢？那么，我们首先呢，定义一个活动服务的最开始时间ei。以及活动活的最开始最迟开始时间li关键活动呢，就是活活动的最早开始时间。

等于最迟开始时间，那么称之为关键活动，那么事件顶点的最早发生时间为veg。世界景点的最迟发生时间呢，为vl k假设。di调弧为JK，则对di上活动而言，ei=v一。g比如说它的最早开始时间活动的，最早开始时间等于事件的最早发生时间。活动的最迟开始时间等于vl k，就等于事件的最迟发生时间，减去我们活动的持续时间。那么，这是我们它的这样一个计算方式，

就是我们质量弧这样一个它的它的。这样一个ve I和li，它的计算的这样一个方式，那么事件顶点发生时间的计算公式呢？是最开始的时间ve原点是？是0 ve k=max vej+dut gk。就是说veg的。最早开veg的，最早开最ve事件，事件g的最早。发生时间加上g。到k。它的这样一个持续时间当中呢，取最大值的这样一个最大值的这样一个情况，这是它的最早开始时间。

最迟开始时间呢，是vo会点等于ve会点vlg，那么这是事件的。事事件顶点的最迟发生时间等于vl k。减去dut gk=vl k，它的这样一个底位点。这样一个。k的这样一个最最迟发生时间减去。g到k的这样一个持续时间，当中的这样一个最小值就是它的这样一个最迟开始时间。那么，我们来看一下这样一个例子。首先呢，我们要计算ve和vl，首先呢，

我们a。a的。那么，我们首先呢，把它写为零。把它写为0a的a为0a的最最早开始时间呢，最早发生时间是零。那么b的最早发生时间呢？是a是我们a的最早。发生时间。加上。那是a的最早发生时间，加上了我们。a到b的。那么是我们aav到a到b的这样一个。

最迟最早的这样一个发生时间，这样一个持续时间，那么取最大值，那么b呢？那么就是六。然后我们再看一下c呢，就是四。那么，到一到d的时候呢？就是五那么到f的时候呢？那么就是五+5+2。那么等于七。那么到。那么到e的时到e的时候呢？到e的时候呢？

到一的时候，那么这个时候呢，我们选择的是。v.这一个b到一的。b的最早开始时间，那么b到e的这样一个持续时间，那么加上了b的最早最早开始时间和c到e的最早开始时间，那么加上。c的CC的最大开始时间呢，加上c到一的持续时间，那么那么它取最大值，那么就是七。那么，同样的f呢？

那么。就是七那么g呢？那么就是15h呢？那么就是14。那么k呢？那么就是18，那么这个时候我们再进行一个。往回的这样一个。计算的这样一个方式，那么就往回的这样继续的这样一个推算的方式，那么接下来呢，我们继续那么这样一个。向前的这样一个运算的，这样一个方式，那么k呢是18，

然后呢h。那么，我们把它写作18那么g呢g呢？那么hg呢？那么就是k-k的这样一个最迟开始时间减去它的这样一个持续时间呢？取最小值了嘛？就是16。那么h呢？就是14那么接下来再看ee呢？我们需要最迟。就是g的最早最迟开始时间那么减去。八减去它的持续时间，那么和h的最迟开始时间，减去它的持续时间，那么来来取这个最取最小值。

那么就是七。那么，接下来再看一下b。b呢，那么就是六那么减一减去一就是六c呢？也是六。那么f呢，就是h呢来减去四。那就是十。那么a1呢？那么就是零。那么从这里呢，我们就可以看到。那么接下来呢？我们再用我们得到的事件顶点的最早发生时间和最迟发生时间来计算边的。

最早。开始时间就是我们活动的最早开始，弧的最早活动，弧弧弧的最早活动时发生时弧最早。开始时间和它的最迟开始时间，那么我们来看一下。首先呢？那么，我们可以得到它的这样一个弧的。最早开始时间和它的最迟开始时间，那么按照这样一个。部分的那么计算出来的结果了，那么我们可以得到这样一个方式，得到这样一个方面，那么我们可以看到弧活动活动弧的最早开始时间。

和最迟开始时间相同的这些部分呢，那么就是abbe。eh?HK，那么这些呢？它的最早开始时间和最迟开始时间是相同的，那么我们说。最早活的最活动的最早开始时间等于最迟开始时间，那么这个时候呢？这个这样的这这样的活动呢？称之为关键活动。那么所以说我们的abbe。ehh k那么这些呢？就称为我们的关键路径，那么也就是说我们的。

关键路径呢，那么也就是说我们的关键路径呢，就是我们的。活动就是我们的活动呢，它的最早开始时间，那么等于最迟开始时间的这样一个部分，那么由于呢，整个工程只有一个开始点和一个完成点。那么，所以在正常的情况下呢？网中只有一个入度为零的点，称为原点，也可以一个初度为零的点，称为汇点。那么，

在AOE网中呢？一条路径上，各全值之和成为该路径的带全路径长度，要估算整项工程的最短完成时间呢？就是要找一条从原点到汇点的带全路径长度最长的路径。成为关键路径。关键路径上的活动呢？称为关键活动。这是这些活动呢？是影响工程进度的关键。那么这些呢？这样呢？我们找到的关键路径呢？就是ab be eh和HK那么这样一个关键路径，那么我们看一下这样一个题，

对于AOE网的关键路径，那么什么是正确的？对于任何一个关节活动提前。整个工程呢，一定会提前完成，这样也不一定完成整个工程最短时间呢，是从原点到会点的最短路径长度。那么。那么这样呢，那么也是不一定的，那么需要是最长的路径长度。一个AOE网的关键路径一定是唯一的，那么关键路径呢？可以是不唯一的任何一个活动时间的改变呢？可能会影响关键活动，

关键路径的改变，那么这个呢？是有可能影影响它的关键路径的改变的。那么，这个题的正确答案呢？那么就是d那么就是选择d选，以后选择d。那么，接下来我们再看一下最短路径，那么最短路径是什么呢？从a地到b地可以有多条路径，有的号是九，但乘客少无换乘。有的可以直达，有的可以换乘，

但是不拥堵，整体耗时较短，在各种方案中呢，乘客往往会根据需要选择一个最佳方案，那么这个问题呢，转换成图之后呢，就是求求最短路径。我们首先来看一下，从单元点到其他顶点的最短路径，假设要从一个定点呢，去往其他多个不同的地点，那么比如说以家为起点，那么重点可是学校，公园，商场。

以及呢，可可能去其他各种地方，将每个景点地点呢，视为图中的一个顶点，那么这种情况呢，抽象为研究有向往中，从原点到其他顶点的最短路径的问题。那么，解决从单元点到其他顶点的最短路径的问题呢？我们通常呢，采用第一节特斯拉。算法一节，特斯拉算法的思想呢，是设gve，是一个代全扭向图，

把图中顶点集合v分成两组，一组呢为已求出最短路径的顶点gs，另一组呢为未确定最短路径的顶点gs。和u初始时s=v之后呢，按最短路径长度的递增次序，每求得一条最短路径v到k就将k呢加入到集合s中。直到全部顶点的都加入到s中，算法结束好吧，我们再看一下它的这样一个算法设置辅助数组d dist，它的每一个分量呢dist。I表示，从当前找到的原点v0到终点VI的最短路径的长度，那么初始状态呢？是从原点v0到VI有边。dst I呢？

为该边上的全值，若从原点v0到顶点VI无边d stil为最大为。无穷大那么初始化，最开始呢v0s当中呢就就就有就就有这样一个，就有这样一个v0。那么dis的g呢就是h零零g，那么这条边它的这样一个长度找出最这样一个边，那么找出最短路径对应的这样一个k disk呢？dsd k呢等于minds=ii呢属于v-ss呢那么。包含于属于b上我们的k了那么。那么。变为我们的s，对于每一个I属于v-s呢进行修改dis ti。我们把它改为minds tid is dk，加上ag ki。

那么，进行这样一个方式，那么第四步呢？进行判断，如果s=v，那么算法结束，否则呢，回到之前的步骤了，那么继续进行这样一个转换。那s列的顶点呢，是已经找到的最短路径的顶点v0到w的最短路径呢，只能通过s集中的顶点。那么dw可能改变，那么if du+e huw小于dw，那么dw呢？

等于du+huw，那么这是我们改改变的这样一个运用的这样一个方式。那么，我们首我们来看一下这些。我们来看一下这样一个过程。那么首先呢，我们最开始呢？v0。到v1，vv 1。v0到v1。那么这个时候呢，它的距离是13v零到v2，它的距离呢，是8v零到v3，

那么它的它没有这样一个路径。那么，距离是无穷大，那么v0到v4呢？它的距离呢？是30，那么到V5呢？是无穷大，那么到v6呢？是32。那么，接下来我们看一下第二步。第二步呢，我们就。找到。

最小的这样一个八的最小这样一条。那么我们就找到最小的这样一个，那么第二步呢？我们就找到呃这样一个。实现的用的这样一个使使用的。那么，采取这样一个实现方式的。联系的这样一个具体的八的这样一个数字，那么就找到八这样一个数字，那么我们接下来呢？第二步呢？那么就是找到这样一个。使用的这样一个距离的这八的这样一个部分，那么就从v2这样一个。类型的起点呢？

那么从这样一个顶点呢？运用运用开始，那么从v2呢？那么到v3呢？有距离。v2呢？到v3有路径，那么就把这样一个v0到v3的路径呢？改改为了v0v2v3，把它的距离呢？设为13。那么，接下来第三，第三步，第三步呢？

我们找到这样一个最短最短的这样一个。我假如让你短的路径。13，13呢？那么v0到v1那么到V5了就有路径，那么它的距离呢？是22，那么我们从vvv 3v1出发v0到v1那么？我们经过了vv 1这个点，那么v0呢？从v0出发，那么这个时候呢，要到达V5，那么我们。从v3呢？

那么可以呢？指指向这样一个触发到触发到我们V5的这样一个部分，那么它的距离呢？那么就是22，然后我们看一下第四步。第四步呢，再找到这样一个13的，这样一个部分，找到这个13呢，我们再从v3这样一个顶点呢，那么触发到v4那么这样一个顶距离呢，就是v0v2v3v4，那么它距离呢，就是19。那么这样呢，

我们就通过这样一个方式接下来呢，我们再找到。我们。19的这样一个值的，这样一个部分，那么我们。从十我们19了，那么可以从v4这样一个顶点出发，那么到达V5，那么它的距离呢？就是就是我们这样一个路径v0v2v3v4V5，那么它的距离呢？是21。那么，这是我们。

这样一个查找找找到它的最短路径的这样一个方式。那么接下来呢？那么这样呢？就是我们迪杰特斯拉那么来寻找我们单元点到其他。各顶点那么的最短路径，那么采取的这样一个方式。那么，它的算法呢？用图，用代权连接矩阵存储AD。数组dist呢，存放当前找到了从原点为零到各个终点的最短路径长度，那么其出态呢，为图中直接路径全值。数组pre呢表示，

从v0到各终点的最短路径上，此项此顶点的前一顶点的序号，若从v0到某终点无路径呢，则用v0作为其前一顶点的序号。好吧，我们看一下这个算法。那么，这是我们采取这样一个矩阵呢？在中间矩阵采取这样一个实现方式，那么实现这样一个？运运用运用方法的这样一个实现的这样一个方式。好了，我们可以看一下，那么接下来呢，我们讲一下每一对顶点之间的最短路径，

每一对顶点之间的最短路径呢，它有两种方法，第一种呢是每次以一个顶点为原点。重复执行集结特斯拉算法n次，那么这个时候它的时间复杂度呢？就是t no 3。第二种方法呢，是采取弗洛伊德算法。弗洛伊德算法呢，它的算法思想呢，是逐个顶点试探法，它的方式呢，是初始时设置一个n阶方阵。并其对角线元素为零，若存在弧viv g，

则对应元素为全值，否则为无穷大，那么逐步呢，在原直接路径中呢，增加中间顶点。若加入中间顶点后，路径变短则修改，否则呢，维持原则，那么直到所有顶点呢，那么全部是全部呢，测试完毕，那么运行完运用完毕。全部呢？实施完毕，

那么实现完毕，那么算法结束，那么这是我们的弗洛伊德算法。那么也就说，弗洛伊德算法呢？是采用。插入点的方式。向我们的路径中呢，插入点的方式啊，来查找。我们各各对顶点之间的最短路径。那么图呢？用临界矩阵存储认识了存放最短路径长度，而pass ig呢？是从v到gv I到vg的最短路径上。

vg的前一点点序号。那么我们可以了，通过这样一个。逐步插入插入点顶点的方式呢来查看来寻找我们各对顶点之间的最短路径。好同学们，那么今天呢？我们给大家讲了一下关于我们图的这样一个应用知识啊，我们来总结一下。图呢，是一种复杂的线性，非线性数据结构。那么主要呢，它有很多它有很多种运用，比如说我们的关键路径，最短路径，

最小生成数，那么这样一些部分。根据不同的分类规则，呢图分为多种类型，无像图，有像图，完全图，连通图，强连通图，带全图，稀疏图和稠密图。临界点路径，回路度连通，分量生成数呢，是在图的算法设计中常用到的这样一个重要术语。

图的存储方式呢，有两大类，以编辑和的方式呢表示以及以及呢，以链接表示连接方式的表示法。其中呢，以编辑和表示的方式呢，为临界矩阵，以链接表方式表示的包括临界表，十字链表以及临界多重表。临接矩阵呢，借助二维数组来表示元素之间的关系实施起来呢，比较简单。临接表十字链表和临接多重表呢，都属于链式存储结构。实现起来比较复杂，

在实际应用中呢，具体采用哪种存储方式，那么可以根据图的类型和实际算法的基本思想来进行选择。那么，我们来看一下临界矩阵和临界表的比较，那么临界矩阵呢？临界矩阵当中无向图的临界矩阵。它是一个对称矩阵，那么可进行，可以进行压缩，压缩到二分之n乘n减一个单元。而有向图呢，是临界矩阵呢，但是它它的临界矩阵呢，不对称，

那么要存储n平方个单元。我们的临界表呢？它的无效图存储n加二一个单元，而有效图呢？存储n+1个单元。那么，我们来看一下临界矩阵和临界表，它的时它的这样一个时间的这样一个使用的这样一个情况。比如说在求某个顶点v的度的时候呢，无效图呢，扫描临界矩阵中序号。这样一个对应的一行，它的时间复杂度呢是on。有向图了，求初度了，

要扫描矩阵中的一行。求入度呢，要扫描矩阵中的一列，它们的时间复杂度呢，都是on而临界表呢。它要求某个顶点的度就要扫描它的边表。最坏的情况呢，它的时间复杂度呢，是on on而有向图呢，它的临界表呢，要求某个顶点的度。求初度呢，就要扫描它的边表，求入度呢，就要按顶点表顺序来扫描所有的边，

那么这是它的这样一个。求求度的这样求它的度的这样一个情求顶点的度的这样一个情情况，那么在如果要求边的数目呢？连接矩阵呢。就直接扫描临界矩阵。采用临界矩阵的时候呢，就直接扫描临界矩阵，它的这样一个时间复杂度呢，是on的平方，采用临界表的时候呢，有效无效图呢，是按。顶点表顺序扫描所有的边表，它的时间复杂度呢？是on加二一而有效图呢？

要按顶点表的顺序扫描所有边表，它的有它的时间复杂度呢？是on+1。那么，我们要判断是否有一条边存在，比如说viv j这条边呢？是否存在？那么这个时候呢，用采用临界矩阵表示的时候呢，我们直接检查临界矩阵aij的原。元素的值啊，它的时间复杂度呢是o1。而采用临接表的时候呢，需要扫描VI的边表，那么最坏的情况呢？

是on那么是判断了o。viv机呢？是否存在的这样一个是否编呢？是否存在的这样一个方式？我们的临界矩阵呢？适用于它的适用情况呢？是适用于稠密图。而临接表呢，它适用情况呢，是适用于稀疏图，那么这是临界矩阵和临界表呢，它的空间。时间以及呢，适用情况的这样一个比较，那么接下来我们回顾一下图的便利，

图的便利算法呢，是实现图和其他运算的基础。图的便利算法有两种深度优先，便利搜索和广度优先搜索，便利深度优先搜索，便利了类似于数的先续便利。借助于债来实现递归广度优先，搜索便利了类似于图的层次便利。借助队列来实现。那么，两种电力方法呢？它的不同之处呢？仅在于对在对顶点访问的顺序不同。那么，时间复杂度呢？

是相同的。用临界表存储的时候呢，时间复杂度为on的平方，用临界表存储的时候呢，时间复杂度呢，为on+1，那么这里大家要记住我们的。图的深度优先搜索便利了，采用的呢是借采用的呢是债的结构来实现，采用的是递归的方式。而图的广度优先，搜索便利呢，是借助于队列这个结构来实实现，也就说深度优先便利采用的是。债这个递归的方式来实现，

而广度优先便利呢？是采用的是对立，那么这样一个方式来实现。那么，我们来看一下图的应用的这个部分图的应用呢？包括了最小生成数，最短路径top排序和求解关键路径。构造最小生成树了，有prem算法和克鲁斯卡尔算法。prime算法，它的核心思想呢，是归并点，实际上复杂的输入了是on的平方，适用于稠密图。克鲁斯卡尔算法呢，

是归并边时间复杂度呢，是o1 log 1适用于稀疏批数网。最短路径算法呢，一种是迪杰特斯拉算法，是求某个原点的，到其余各点的最短路径。求解过程呢，是按路径长度递增的次序呢，产生最短路径，时间复杂度呢，是on的平方。另外呢，我们还可以求每对顶点之间的最短路径，这样这这种时候呢，我们就可以将集结。

特斯特斯拉算法呢？重复n次，重复n次，比如说我们可以对每个顶点呢，都实实行一次，都都采用一次。理解特斯拉算法，这样呢，它的时间这样呢，它的时间复杂度呢，是on的三次方，还有一种方法呢，是flow 1的算法。它的时间复杂度呢？也是on的三次方。

那么top排序和关键路径呢？都是有效无环图的应用。top排序是基于用顶点表示活动的有效图，就是我们的a uv网。那么，对于不存在环的有向图呢？图中的所有顶点呢？能够排序的线性序列，那么top排序呢？是不唯一的。关键路径算法呢，是基于用弧表示活动的有线图，那么就是我们的aue网关键路径上的活动呢，叫做关键活动，那么这些活动呢，

是影响工程进度的关键。他们的提前或拖延呢，将是整个工程提前或拖延关键路径呢，是不唯一的关键路径的算法呢，是实现top排序的基础上呢，用零基表表示图关键路径的算法，实现复杂度呢，是on。加一那么这样呢，那么今天呢，我们所讲的呢，就是主要是图的基本概念和术语以及呢。图的四种存储表示，那么以及呢？图的两种便利算法和图的最小甚至数算法最简最短路径算法和top排序算法和我们的关键路径算法。

那么大家下来的时候呢，那么再看一下这些部分进行一个了解和熟悉好，同学们，今天呢，我们的课呢，就讲到这里好，谢谢大家。

		自动登录	找回密码
密码			立即注册