求关键路径是以拓扑排序为基础的

拓扑排序是指将有向无环图(DAG)中的所有顶点排成一个线性序列，使得对图中的任意两个顶点u,v,如果存在一条有向边从u指向v,那么在序列中u就排在v的前面。拓扑排序不仅仅是一种排序算法，更是许多算法的基础，其中求关键路径就是以拓扑排序为基础的一种重要算法。下面我将从多个角度分析为什么求关键路径是以拓扑排序为基础的。

一、拓扑排序解决了什么问题？

拓扑排序是解决一些依赖关系的问题的常用手段，如工程项目中不同工作任务的前置要求。前置要求就是指当一个任务A必须在另一个任务B之前完成时，我们就说A是B的前置要求。利用拓扑排序，我们可以将每个任务看做一个结点，每个前置要求看成一条边，从而将整个项目转化为一个有向无环图(DAG)，用拓扑排序可以获取所有结点的线性序列，根据它的顺序可以来确定工作任务的执行顺序。

二、关键路径的概念是什么？

在一个任务之间，不同的前置要求可能产生不同的时间消耗，因此，对于一个工程项目，确定哪些任务是最关键的就变得很重要，这些任务的完成时间将直接“影响”到整个工程项目的完成时间。而关键路径的概念就应运而生。关键路径是指所有任务中，完成所需时间最长的路径。可以看作是一个或多个任务构成的序列，他们的完成时间导致了整个项目的完成时间。

三、关键路径的求解方法

求解关键路径的方法非常多样，例如动态规划、回溯算法、贪心算法等等。而在这里，我们主要讲述基于拓扑排序实现的关键路径的求解方法。

1、首先，确定完成每个任务所需的时间，连接任务形成一个DAG(有向无环图)。

2、计算DAG中所有任务的入度，即进入该点的另一个点的数量。

3、选择入度为0的任务作为起始点，标记该点并入队。

4、从队列中取出某一个点，将所有从该点出发的边上的另一个点的入度减去1，表示该点的入口少了一个，若此时入度为0，则标记该点并入队。

5、重复执行步骤4，直到队列为空。

6、从标记的任务中，确定完成时间最长的任务作为最后一个任务，借助最后一个任务可以回推整个路径，并确定所有关键任务的完成时间。