2022.11.09课后——数据结构笔记

主要分为两部分，第一部分关于拓扑排序；第二部分关于关键路径

拓扑排序（AOV-网的相关基本思路）

利用图进行拓扑排序（排序结果不唯一）

首先找到图中入度为0的结点，将他们存储到拓扑排序的数组中；（重复此步骤即可，要明确图的作用，是的结果并不唯一）

利用邻接表进行拓扑排序（排序结果一定唯一）

一般在做题过程中，会给出一张邻接表，要求我们按照拓扑排序的方法将其输出出来。

同样地，第一步还是找到入度为0的结点，有时不会给出每个结点的入度值，需要我们自己去根据图片获得相应信息，如上图所示：自上而下的话，他们的入度值依次为：0，2，1，3，1

然后将所有入度为0的结点依次放到栈里面，如果栈不为空，且外面不再有入度为0的结点，那么，就需要进行栈顶元素出栈操作，并将栈顶元素后面跟着的几个元素的入度数均减1；（重复此操作，知道所有元素均输出完成即可）

那么，上图中的答案是多少呢？

关键路径（AOE-网的相关基本思路）

首先需要明确，关键路径不止一条！

一般情况下，题目中会给出这样一张图片，要求我们根据所学知识求出关键路径。

第一步，我们要根据图片找到Ve(i)和Vl(i)，前者简称最早完成时间，后者简称最晚完成时间。

入度为0的点可以叫做源点，它的最早完成时间是0，之后的结点，就是从源点开始往后推的，之后的每一个结点，

Ve(i):其最早完成时间都是由前一个结点的最早完成时间+权值来计算的，若是有两个结点指向的是同一个结点，那么，那么取其中的最大值（其中的最大值才能保证二者都完成了，项目才能继续向下推进）；

Vl(i):其最晚完成时间是从最后一个结点开始推的，最后一个结点的最早和最晚数值一样，往前推的话，需要利用每个结点的后一个结点减去前面的权值，若是一个结点同时指向两个结点，前推时，去其中的最小值（保证项目的进度）

e(i)：这个元素的值的话，就是它的前一个结点的最早完成时间Ve(j)

l(i):这个元素的话，就是e(i)+该结点前面的权值得来的

最后求关键路径的话，只需要将e(i)和l(i)的值作差就好啦！如果差为0，就是关键路径，反之，则为非关键路径

问题来了，上图中的关键路径是什么呢？