数学和计算机科学板块_辛酸网
数据结构与算法15
BY TSherry
拓扑排序是针对有向无环图而言的，对所有结点进行排序。我们知道一条有向边有起点和终点。 就按照这个定义我们说，起点在终点前面，这就是拓扑排序的前后区分标准。
想象一张特别简单的图，里面只有三条边：a→b，c→b与b→d。 因为第一条边中a是起点而b是终点，所以排序中a在b前面。同理c也在b前面，而b在d前面。 a和d之间没有边直连，但是因为b的存在，而前后关系是存在传递性的，故a在d前面，我们可以写出一个序列abd。 但a和c呢？ac之间相互不通，对于这种情况二者实际上无所谓真正的先后关系，是同样靠前的。 因此，对于这种不分前后的结点，在最后的序列里怎么写都行。由此得出从前往后的拓扑排序序列acbd或cabd。
拓扑排序在的每一轮的任务也非常简单：从当前图的残余中，选取一个入度为0的， 写在排序序列里，顺便把这个结点从图中删去。直到整个图全都被写进去为止。 但请注意，拓扑上的前后关系是有传递性和不对称性的，如果a在b前面，b在c前面的话则a一定在c前面。 一旦有边a→b和边b→a，那么一方面a在b前面，另一方面b却要在a前面，这在拓扑排序序列时是不允许的，非常荒诞的。 所以至少在考研的题目里，图的拓扑排序没法针对有环的图搞。
关键路径法是一种高效的工程管理方法，用来寻找一个工程当中最不能耽误的步骤。 这一管理方法最早由美国杜邦公司和美军使用，并在关于工程项目的法律纠纷中被推广使用。
在一个庞大的工程中有若干步骤，有的步骤可以同时进行，而有的步骤存在着严格的先后顺序。 但就时间而言，有一些步骤是最为重要的。 虽然说，只要你时间安排妥当，有一些步骤即使耽误了，拖延了时间，也不会耽误整体的工期， 但也有一些步骤是绝对不能耽误的，否则，一旦这些步骤自身的工作时间被延长，则整体的工程之结束时间必然会被推迟。
在这项庞大的工程中，很多步骤的开始和结束时间存在着相互制约的关系。 举个例子：今有步骤abcde，其中步骤e在abcd都完成后才能启动，并且只要abcd都完成，e可以立刻开始。 已知abcd最早能结束的时刻分别为ta,tb,tc,td。 问：步骤e最早在什么时候可以开始？
既然步骤e在步骤abcd都结束后才能开始， 那么势必要在abcd中的最后一个结束的步骤结束以后，e才能开始。 因此，步骤e最早能够开始的时刻就要在ta,tb,tc,td中取最大值。 同样的道理，这像工程还需要面对另一个问题。今有步骤f,g,h,i都要进行，但是它们都必须在步骤e完成后才能开始。 已知各项客观条件安排要求步骤f,g,h,i最晚必须开始的时刻分别是tf,tg,th,ti， 问：步骤e最晚什么时候就必须结束？
既然步骤f,g,h,i在步骤e完成后才能开始，而步骤f,g,h,i的开始时间又有着最晚限制， 那么这些时间限制也会作用在e上。步骤e最晚必须在第一个必须开始的步骤开始时就得结束。因此，e最晚必须结束的时刻， 就是tf,tg,th,ti里的最小值。
由此可见，步骤e工作的时间段必须在 max{ta,tb,tc,td}到min{tf,tg,th,ti} 之间。不妨设前者为tmustbegin，后者为tmustend， 则e的实际工作的整个时长就不能超过tmustend-tmustbegin，要不然就得延误工期。 就这还得是前面abcd这4个步骤以及后面fghi那4个步骤对e造成的限制，还不包括e自身的内部限制。 如果现在各项客观条件使得步骤e最短也得消耗tprocess的时间， 那我们还得看tmustend-tmustbegin这个时间窗口能不能容纳下process的时间消耗。 如果能，就说明步骤e有可能做到，要不然步骤e就完不成，因为时间不够，进而整个工程就干不了了。
倘若出现这样一种情况：
时间窗口tmustend-tmustbegin和最短能保证的时间消耗tprocess恰好相等，
或是大了那么一点点，那情况就比较棘手了。在实施步骤e时我们必须神经紧绷，不能出现什么大的差错，要不然步骤e无法按时完成，
相应的后面的步骤就得晚开始，整个工期就延误了。此时e就叫这项工程的关键步骤。从前往后，从一开始工程启动的起点，
到最后项目完成的终点，关键步骤连起来就是一条关键路径。
在图论中的内容往往是理想化的，对于一个步骤e， 如果时间窗口tmustend-tmustbegin和最短能保证的时间消耗tprocess恰好相等， 则这个步骤就是图中的关键步骤。在关键路径法这种工程管理方法中，施工方需要画出一种特别的有向图。 图中每一条边代表一个步骤本身，每一个结点代表着步骤的开始与结束，边的起点即为步骤开始，边的终点即为步骤结束。 最开始的起点对应了整个工程的开始，最后的终点昭示着项目的竣工。
见下，结点*一方面象征了步骤d的结束，另一方面象征了步骤efg的开始。而结点@宣告了步骤efg的结束与步骤i的开始。
要知道关键路径长什么样子有两种求法，一种是从前往后找，一种是从后往前找。 整体上我们要先知道这个项目在什么时候启动，什么时候必须完成。然后看图中的每一条边。
第一种方法思路是这样的：客观条件造成的某步骤最晚能够开始的时间，加上该步骤必须消耗的时间就等于最晚能够结束的时间， 如果最晚能够结束的时间恰好等于最晚必须结束的时间，则该步骤属于关键路径。 然后以看这条边终点作为起点的边，一步一步，从前往后依次计算步骤的结束能否拖延，直至整个项目的完成。
第二种方法思路是这样的：甲方要求和其它条件造成的某步骤最早必须结束时间， 减去所需要消耗时长就等于其最早必须开始的时间，如果刚好等于最早能够开始的时间，则该步骤为关键步骤。 接着看以该步骤起点为终点的前面步骤，从后往前一步步看步骤的开始能否提早，直至整个项目的启动。
关键路径代表了项目中的时间核心部分。关键路径法一方面告诉了我们哪些地方可以偷懒磨洋工， 以及能磨多少洋工，另一方面也告诫我们哪些地方不能马虎，不得有所拖延，否则整个工程就无法按时完成。
辛酸网 ©版权所有