数据结构：图的应用(二)

三、有向无环图描述表达式有向无环图简称DAG图是指一个不含任何有向环路的有向图。考点构建表达式的有向无环图例如表达式首先画出二叉树描述表达式有向无环图描述表达式表达式中出现几个元素就出现几个元素结点公共表达式只出现一次。如图abcde五个元素且父结点的入边共享。我不知道怎么讲这个怎么画我只能画出来我画的时候是先把所有元素写出来先从最优先的开始符号画之后画的时候注意已经出现的元素是否有能够替代的如果有就直接画符号将两个式子连在一起中间只要涉及与abcde元素的式子直接连到元素上即可关键是找是否有能替代的元素或式子。讲的有点赘余多练一练就好了。注意在表达式的有向无环图表示中不会重复出现的操作数顶点。大家结合下面的图看一下同种颜色就是重复的变换的时候把重复的减去即可。四、拓扑序列AOV网首先是一个有向无环图结点代表活动边代表活动进行的先后顺序有向边是的直接前驱是直接后继任何活动都不能成为自己的直接前驱或直接后继。在图论中拓扑排序指的是由有向无环图构成的一个线性序列该序列满足条件每个顶点只出现一次若存在从顶点A到B的路径则在排序后的序列中B必须在A之后。每个AOV网都有一个或多个拓扑排序序列。考点1拓扑排序可以找到图中的环拓扑排序方法是找取一个没有前驱的顶点并输出之后删除该顶点及其以他为起点对应的边之后重复上述步骤直到当前AOV网为空或者无法再找到入度为0的边。如果出现后一种情况则代表这个图不是有向无环图。考点2不同存储方式下的拓扑排序效率采用邻接表时间复杂度为采用邻接矩阵时间复杂度为考点3深度优先搜索DFS实现拓扑排序在拓扑排序的DFS实现中我们采用后序遍历从某个起点深入直到叶子节点无后继节点在递归返回时依次记录节点最终逆序这些记录即得到拓扑排序。逆拓扑排序从AOV网中找出度为零的顶点输出删除该点和所有以他为为终点的有向边重复上述操作直到AOV网变空为止。拓扑序列唯一的充要条件每次输出顶点的时候当前入度为零的顶点都恰好只有一个最终拓扑序列唯一。AOV网中各顶点地位平等根据拓扑排序的结果对定点重新编号使得新邻接矩阵成为上三角矩阵。反之有向图对顶点重新编号其邻接矩阵能够转换为上三角矩阵则该图一定是有向无环图因而存在拓扑序列。五、关键路径对于关键路径wd书上在所有从源点到汇点的路径中路径长度最大的那条路径被称为关键路径把关键路径上的活动称为关键活动。但是书中加黑字体又写完成整个工程所需的最短时间等于关键路径的长度即该路径上所有活动的持续时间之和。十分有九分的不对劲。请教了以下deepseek举了一个好吃的栗子。木桶效应大家都听过一个木桶能装多少水取决于木桶中最短的那根木板同样一个工程取决于最关键的那个活动什么时候结束。摘用一下deepseek关键路径法中“路径长度最大”指的是所有路径中持续时间之和最大的那条路径而“所需最短时间”指项目理论上能完成的最早时间。两者相等的原因在于工程必须等所有路径上的工作都完成后才能结束因此工期由最长的路径决定最短也不可能比它更短。希望大家能搞懂上面的引入AOE网结点代表事件边代表活动边上的权值代表完成该活动所需要的时间开销结点代表的事件发生之后从该结点出发的各个有向边代表的活动才能开始只有当进入结点的各个有向边的活动都完成后该结点代表的事件才可以发生。关键路径中有五大小可爱其实一点也不可爱事件最早发生时间从源点到事件所有路径中最长路径事件最晚发生时间从汇点到该结点往回推的所有路径中最短的路径活动最早开始时间该活动起始结点对应的活动最迟开始时间该活动对应的尾结点的减去该活动的路径长度时间余量满足的活动称为关键活动。一个活动的时间余量为零则该活动必须如期完成否则将导致整个工程延期。注意关键路径上的活动均为关键活动关键路径不止一条只有加快那些同时出现在所有关键路径上的关键活动才能达到缩短工期的目的。没有举例子时间不太够了放个小链接。