个人开发网站,网站空间到期提示,wordpress 列表页,娱乐网站 建站软件目录结构 注#xff1a;提前言明 本文借鉴了以下博主、书籍或网站的内容#xff0c;其列表如下#xff1a; 1、参考书籍#xff1a;《算法导论》第三版 就是这本被封神的杰作#xff0c;就是它#x1f926; 2、参考书籍#xff1a;《数据结构》严奶奶版 3、参考书… 目录结构 注提前言明 本文借鉴了以下博主、书籍或网站的内容其列表如下 1、参考书籍《算法导论》第三版 就是这本被封神的杰作就是它 2、参考书籍《数据结构》严奶奶版 3、参考书籍《数据结构》(用面向对象方法与C语言描述) 第二版 殷人昆版 4、参考书籍《数据结构》(C版) 第三版 邓俊辉版 5、华中科技大学 有向无环图及应用 公开课点击前往 6、OI Wiki 有向无环图点击前往 7、OI Wiki 拓扑排序点击前往 8、关键路径 拓扑排序点击前往 DSA 经典数据结构与算法 有向无环图 文章快速说明索引有向无环图的背景拓扑排序逆拓扑排序AOV 网关键路径和 AOE 网 文章快速说明索引
学习目标
前言还记得在大学的时候数据结构作为计算机科学与技术专业最重要的一门课 当时学校采用的教材是严奶奶的粉红色那本不过当时是真的不愿多看一眼 苦涩难懂 又非常深奥满篇伪代码实现的例子和夏日那十分惬意的下午 简直让人头大而晕 也可能是上学那会儿年少浮躁也可能是因为当时的能力比较的菜吧 ┑(Д )┍ 。现在再回头捧读厚厚的《算法导论》竟然有一种说不上来的快乐 沉浸在数据结构和算法之美惊叹于高超技巧式拍案惊奇 学习内容详见目录
1、数据结构与算法(DSA)之有向无环图 学习时间
2024年02月15日 14:17:05 学习产出
1、CSDN 技术博客 1篇 有向无环图的背景
有向无环图(Directed Acyclic Graph)一个无环的有向图。
其性质如下
能 拓扑排序 的图一定是有向无环图如果有环那么环上的任意两个节点在任意序列中都不满足条件了有向无环图一定能拓扑排序归纳法假设节点数不超过 k 的 有向无环图都能拓扑排序那么对于节点数等于 k 的考虑执行拓扑排序第一步之后的情形即可 如何判定一个图是否是有向无环图呢
检验它是否可以进行 拓扑排序 即可当然也有另外的方法可以对图进行一遍 DFS在得到的 DFS 树上看看有没有连向祖先的非树边返祖边。如果有的话那就有环了 接下来看一下 DAG 的应用 如下
一、描述表达式
// 如下表达式含 * 操作((a b) * (b * (c d)) (c d) * e) * ((c d) * e)用二叉树表示这个表达式(21个顶点)如下 用有向无环图表示该表达式(12个顶点)如下 二、表示 AOV网 (Activity On Vertex Network) or AOE网Activity On Edge) 什么是AOV网与AOE网——以及AOV网与AOE网区别和运用点击前往
下面我们再详细介绍它们 拓扑排序
拓扑排序的英文名是 Topological sorting。拓扑排序要解决的问题是给一个有向无环图的所有节点排序。换言之其是一个有向无环图DAGDirected Acyclic Graph的所有顶点的线性序列且该序列必须满足下面两个条件
每个顶点出现且只出现一次若存在一条从顶点 A 到顶点 B 的路径那么在序列中顶点 A 出现在顶点 B 的前面有向无环图DAG才有拓扑排序非DAG就没有拓扑排序一说 一个经典的案例如下 因此我们可以说
在一个 DAG有向无环图 中我们将图中的顶点以线性方式进行排序使得对于任何的顶点 u 到 v 的有向边 (u,v)都可以有 u 在 v 的前面还有给定一个 DAG如果从 i 到 j 有边则认为 j 依赖于 i。如果 i 到 j 有路径i 可达 j则称 j 间接依赖于 i拓扑排序的目标是将所有节点排序使得排在前面的节点不能依赖于排在后面的节点 举一个例子如下
拓扑排序Topological Sorting点击前往 逆拓扑排序
逆拓扑排序的步骤
从AOV网中选择一个出度为0的顶点并输出从网中删除该顶点和所有以它为终点的有向边重复1和2直到当前的AOV网为空 AOV 网
日常生活中一项大的工程可以看作是由若干个子工程组成的集合这些子工程之间必定存在一定的先后顺序即某些子工程必须在其他的一些子工程完成后才能开始。
我们用有向图来表现子工程之间的先后关系子工程之间的先后关系为有向边这种有向图称为顶点活动网络即 AOV 网 (Activity On Vertex Network)。一个 AOV 网必定是一个有向无环图即不带有回路。与 DAG 不同的是AOV 的活动都表示在边上。
在 AOV 网中顶点表示活动弧表示活动间的优先关系。AOV 网中不应该出现环这样就能够找到一个顶点序列使得每个顶点代表的活动的前驱活动都排在该顶点的前面这样的序列称为拓扑序列一个 AOV 网的拓扑序列不是唯一的由 AOV 网构造拓扑序列的过程称为拓扑排序。因此拓扑排序也可以解释为将 AOV 网中所有活动排成一个序列使得每个活动的前驱活动都排在该活动的前面一个 AOV 网中的拓扑排序也不是唯一的。
前驱活动有向边起点的活动称为终点的前驱活动只有当一个活动的前驱全部都完成后这个活动才能进行后继活动有向边终点的活动称为起点的后继活动
检测 AOV 网中是否带环的方式是构造拓扑序列看是否包含所有顶点。构造这个拓扑序列步骤
从图中选择一个入度为零的点输出该顶点从图中删除此顶点及其所有的出边重复上面两步直到所有顶点都输出拓扑排序完成或者图中不存在入度为零的点此时说明图是有环图拓扑排序无法完成陷入死锁 关键路径和 AOE 网
与 AOV 网对应的是 AOE 网Activity On Edge Network) 即边表示活动的网。AOE 网是一个带权的有向无环图其中顶点表示事件弧表示活动持续的时间。通常AOE 网可以用来估算工程的完成时间。AOE 网应该是无环的且存在唯一入度为零的起始顶点源点以及唯一出度为零的完成顶点汇点。 AOE 网中的有些活动是可以并行进行的所以完成整个工程的最短时间是从开始点到完成点的最长活动路径长度这里所说的路径长度是指路径上各活动的持续时间之和即弧的权值之和不是路径上弧的数目。因为一项工程需要完成所有工程内的活动所以最长的活动路径也是关键路径它决定工程完成的总时间。 AOE 网的相关基本概念如下
活动AOE 网中弧表示活动。弧的权值表示活动持续的时间活动在事件被触发后开始。事件AOE 网中顶点表示事件事件能被触发。 弧活动aj 的最早开始时间初始点到该弧起点的最长路径长度记为 e(j)。弧活动aj 的最迟开始时间在不推迟整个工期的前提下工程达到弧起点所表示的状态最晚能容忍的时间记为 l(j)。即事件的最迟发生时间 - 弧的活动时间值。 顶点事件vj 的最早发生时间初始点到该顶点的最长路径长度记为 ve(j)它决定了以该顶点开始的活动的最早发生时间所以 ve(j) e(j)。顶点事件vj 的最迟发生时间在不推迟整个工期的前提下工程达到顶点所表示的状态最晚能容忍的时间记为 vl(j)它决定了所有以该状态结束的活动的最迟发生时间所以 l(j) vl(j) - dul(aj)。 关键路径AOE 网中从源点到汇点的最长路径的长度。关键活动关键路径上的活动最早开始时间和最迟开始时间相等(看下面时间余量d(j) 0的)。 最早和最迟发生时间的递推关系 按拓扑顺序求最早是从前往后前驱顶点的最早开始时间与边的权重之和最大者最迟是从后往前后继顶点的最迟开始时间与边的权重之差的最小者。 下面看一个例子计算如下 如上图其其中之一的拓扑排序如下
V1 V3 V2 V5 V4 V6V1V2V3V4V5V6ve(j)事件 的最早发生时间 -0326 max68 maxvl(j)事件 的最迟发生时间 -04 min2 min678
a1a2a3a4a5a6a7a8e(j)活动 aj 的最早开始时间 -00332266l(j)活动 aj 的最迟开始时间 -4 - 32 - 26 - 27 - 36 - 48 - 38 - 28 - 1l(j)活动 aj 的最迟开始时间 -10442567d(j)活动 aj 的时间余量 l(j) - e(j)10110301
于是关键活动有a2 a5 a7。如下 V1-V3-V4-V6 就是关键路径total 8! 关键路径算法
输入 e 条弧 (j,k)建立 AOE 网从源点 v0 出发令 ve[0] 0, 按照拓扑排序求其余各个顶点的最早发生时间 ve[i], (i i n-1)。如果得到的拓扑有序序列中顶点的个数小于网中的顶点数 n则说明网中存在环不能求关键路径算法终止否则执行步骤 3从汇点 vn 出发令 vl[n-1] ve[n-1]按照逆拓扑有序求其余各顶点的最迟发生时间 vl[i], (n-2 i 2);根据各顶点的 ve 和 vl 值求每条弧 s 的最早开始时间 e(s) 和最迟开始时间 l(s)。若某条弧满足条件 e(s) l(s), 则为关键活动。
