前言

部分内容摘自程杰的《大话数据结构》

1. 拓扑排序

1.1 拓扑排序介绍

我们会把施工过程、生产流程、软件开发、教学安排等都当成一个项目工程来对待，所有的工程都可分为若千个 “活动” 的子工程。例如下图是一张电影制作流程图，现实中可能并不完全相同，但基本表达了二个工程和若千个活动的概念。在这些活动之间，通常会受到一定的条件约束，如其中某些活动必须在另一些活动完成之后才能开始。就像电影制作不可能在人员到位进驻场地时，导演还没有找到，也不可能在拍摄过程中，场地都没有。这都会导致荒谬的结果。因此这样的工程图，一定是无环的有向图。
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网（ Activity On Vertex Network）。AOV网中的弧表示活动之间存在的某种制约关系。比如演职人员确定了，场地也联系好了，才可以开始进场拍摄。另外就是AOV网中不能存在回路。刚才已经举了例子，让某个活动的开始要以自已完成作为先决条件，显然是不可以的。

设G=(V,E)是一个具有n个顶点的有向图，v中的顶点序列v $_0$ ，v $_2$ ，···，v $_n$ ，满足若从顶点 v $_i$ 到 v $_j$ 有一条路径，则在顶点序列中顶点 v $_i$ 必在顶点 v $_j$ 之前。则我们称这样的顶点序列为一个拓扑序列。
上图这样的AOV网的拓扑序列不止一条。序列 v $_0$ v $_1$ v $_2$ v $_3$ v $_4$ v $_5$ v $_6$ v $_7$ v $_8$ v $_9$ v $_{10}$ v $_{11}$ v $_{12}$ v $_{13}$ v $_{14}$ v $_{15}$ v $_{16}$ 是一条拓扑序列，而 v $_0$ v $_1$ v $_2$ v $_3$ v $_4$ v $_5$ v $_6$ v $_7$ v $_8$ v $_9$ v $_{10}$ v $_{11}$ v $_{12}$ v $_{13}$ v $_{14}$ v $_{15}$ v $_{16}$ 也是一条拓扑序列。
所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环（回路）的AOV网；如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环（回路），不是AOV网。
一个不存在回路的AOV网，我们可以将它应用在各种各样的工程或项目的流程图中，满足各种应用场景的需要，所以实现拓扑排序的算法就很有价值了。

1.2 拓扑排序算法

对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为 0 的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为 0 的顶点为止。
首先我们需要确定一下这个图需要使用的数据结构。前面求最小生成树和最短路径时，我们用的都是邻接矩阵，但由于拓扑排序的过程中，需要删除顶点，显然用邻接表会更加方便。因此我们需要为AOV网建立一个邻接表。考虑到算法过程中始终要查找入度为 0 的顶点，我们在原来顶点表结点结构中，增加一个入度城in，结构如下表所示，其中in就是入度的数字。
因此对于下图的第一幅图AOV网，我们可以得到如第二幅图的邻接表数据结构。

typedef struct EdgeNode	/* 边表结点 */
{
	int adjvex;	/* 邻接点域，存储该顶点对应的下标 */
	int weight;	/* 用于存储权值，对于非网图可以不需要 */
	struct EdgeNode *next;	/* 链域，指向下一个邻接点 */
}EdgeNode;

typedef struct VertexNode	/* 顶点表结点 */
{
	int in;					/* 顶点入度 */
	int datap				/* 顶点域，存储顶点信息 */
	EdgeNode *firstedge;	/* 边表头指针 */
}VertexNode, AdjList[MAXVEX];

typedef struct
{
	AdjList adjList;
	int numVertexes,numEdges;	/* 图中当前顶点数和边数 */
}graphAdjList,*GraphAdjList;

在算法中，我还需要辅助的数据结构——栈，用来存储处理过程中入度为 0 的顶点，目的是为了避免每个查找时都要去遍历顶点表找有没有入度为 0 的顶点。
现在我们来看代码，并且模拟运行它。

/* 拓扑排序，若GL无回路，则榆出拓扑排序序列并返回OK,若有回路返回ERROR */
Status TopologicalSort ( GraphAdjList GL)
{
	EdgeNode *e;
	int i,k,gettop;
	int top=0;		/* 用于栈指针下标 */
	int count=0;	/* 用于统计输出顶点的个数 */
	int stack;		/* 建栈存储入度为0的顶点 */
	stack= (int *)malloc(GL->numVertexes * sizeof(int));
	for(i = 0; i<GL->numVertexes; i++)
	{
		if (GL->adjList[i].in == 0)	/* 将入度为0的顶点入栈 */
			stack[++top]=i;
	}
	while(top!=0)
	{
		gettop=stack[top--];	/* 出栈 */
		printf("%d -> ",GL->adjList[gettop].data);	/* 打印此顶点 */
		count++; 				/* 统计输出顶点数 */
		for(e=GL->adjList[gettopl.firstedge; e; e=e->next )	/* 对此顶点弧表遍历 */
		{
			k=e->adjvex;
			if (!(--GL->adjList[k].in) )	/* 将k号顶点邻接点的入度减1 */
				stack[++top]=k;	/* 若为0则入栈，以便于下次循环输出 */
		}
	}
	if (count < GL->numVertexes) 	/* 如果count小于顶点数，说明存在环 */
		return ERROR;
	else
		return OK;
}

程序开始运行，第 4~8 行都是变量的定义，其中stack是一个栈，用来存储整型的数字。
第 9~11 行，作了一个循环判断，把入度为 0 的顶点下标都入栈，从右下图邻接表可知，此时stack应该为 {0, 1, 3}，即v $_0$ 、v $_1$ 、v $_3$ 的顶点入度为 0，如下图所示。
第 13~24 行，while循环，当栈中有数据元素时，始终循环。
第 15~17 行，v $_3$ 出栈得到gettop=3。并打印此顶点，然后count加 1。
第 18~23行，循环其实是对 v $_3$ 顶点对应的弧链表进行遍历，即下图中的灰色部分，找到 v $_3$ 连接的两个顶点 v $_2$ 和 v $_{13}$ ，并将它们的入度减少一位，此时 v $_2$ 和 v $_{13}$ 的in值都为 1。它的目的是为了将 v $_{3}$ 顶点上的弧删除。
再次循环，第 13~24 行。此时处理的是顶点 v $_1$ 。经过出栈、打印、count=2后，我们对 v $_1$ 到 v $_2$ 、v $_4$ 、v $_8$ 的弧进行了遍历。并同样减少了它们的入度数，此时 v $_2$ 入度为 0，于是由第 21~22 行知，v $_2$ 入栈，如下图所示。试想，如果没有在顶点表中加入in这个入度数据域，21 行的判断就必须要是循环，这显然是要消耗时间的，我们利用空间换取了时间。
接下来，就是同样的处理方式了。下图展示了 v $_2$ v $_6$ v $_0$ v $_4$ v $_5$ v $_8$ 的打印删除过程，后面还剩几个顶点都类似，就不图示了。
最终拓扑排序打印结果为 3->1->2->6->0->4->5->8->7->12->9->10->13->11。当然这结果并不是唯一的一种拓扑排序方案。

分析整个算法，对一个具有n个顶点e条弧的AOV网来说，第 9~11 行扫描顶点表，将入度为 0 的顶点入栈的时间复杂为 $O(n)$ ，而之后的while循环中，每个顶点进一次栈，出一次栈，入度减 1 的操作共执行了e次，所以整个算法的时间复杂度为 $O(n+e)$ 。

2. 关键路径

拓扑排序主要是为解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最短时间问题。比如说，造一辆汽车，我们需要先造各种各样的零件、部件，最终再组装成车。这些零部件基本都是在流水线上同时生产的，假如造一个轮子需要 0.5 天时间，造一个发动机需要 3 天时间，造一个车底盘需要 2 天时间，造一个外壳需要 2 天时间，其他零部件时间需要 2 天，全部零部件集中到一处需要 0.5 天，组装成车需要 2 天时间，请问，在汽车厂造一辆车，最短需要多少时间呢?
有人说时间就是全部加起来，这当然是不对的。我已经说了前提，这些零部件都是分别在流水线上同时生产的，也就是说，在生产发动机的 3 天里，可能已经生产了 6 个轮子，1.5 个外壳和 1.5 个底盘，而组装车是在这些零部件都生产好后才可以进行。因此最短的时间其实是零部件中生产时间最长的发动机 3 天 + 集中零部件 0.5 天 + 组装车的2天，一共 5.5 天完成一辆汽车的生产。
因此，我们如果要对一个流程图获得最短时间，就必须要分析它们的拓扑关系，并且找到当中最关键的流程，这个流程的时间就是最短时间。
因此在前面讲了AOV网的基础上，我们来介绍一个新的概念。在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网（Activity On Edge Network）。我们把AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。由于一个工程，总有一个开始，一个结束，所以正常情况下，AOE网只有一个源点一个汇点。例如下图就是一个AOE网。其中 v $_0$ 即是源点，表示一个工程的开始，v $_9$ 是汇点，表示整个工程的结束，顶点 v $_0$ ，v $_1$ ，···，v $_9$ 分别表示事件，弧 <v $_0$ ,v $_1$ >，<v $_0$ ,v $_2$ >，···，<v $_8$ ,v $_9$ > 都表示一个活动，用 a $_0$ ，a $_1$ ，···，a $_{12}$ 表示，它们的值代表着活动持续的时间，比如弧 <v $_0$ ,v $_1$ > 就是从源点开始的第一个活动 a $_0$ ，它的时间是 3 个单位。

既然AOE网是表示工程流程的，所以它就具有明显的工程的特性。如有在某项点所代表的事件发生后，从该顶点出发的各活动才能开始。只有在进入某顶点的各活动都已经结束，该顶点所代表的事件才能发生。
尽管AOE网与AOV网都是用来对工程建模的，但它们还是有很大的不同，主要体现在AOV网是顶点表示活动的网,，它只描述活动之间的制约关系，而AOE网是用边表示活动的网，边上的权值表示活动持续的时间，如下图所示两图的对比。因此，AOE网是要建立在活动之间制约关系没有矛盾的基础之上，再来分析完成整个工程至少需要多少时间，或者为缩短完成工程所需时间，应当加快哪些活动等问题。

我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。显然就上图的AOE网而言，开始→发动机完成→部件集中到位→组装完成就是关键路径，路径长度为 5.5。
如果我们需要缩短整个工期，去改进轮子的生产效率，哪怕改动成 0.1 也是无益于整个工期的变化，只有缩短关键路径上的关键活动时间才可以减少整个工期长度。例如如果发动机制造缩短为 2.5，整车组装缩短为 1.5，那么关键路径长度就为 4.5，整整缩短了一天的时间。
那么现在的问题就是如何找出关键路径。对人来说，上图第二幅这样的AOE网，应该比较容易得出关键路径的，而对于上上图的AOE网，就相对麻烦一些，如果继续复杂下去，可能就非人脑该去做的事了。

2.1 关键路径算法的原理

为了讲清楚求关键路径的算法，我还是来举个例子。假设一个学生放学回家，除掉吃饭、洗漱外，到睡觉前有四小时空闲，而家庭作业需要两小时完成。不同的学生会有不同的做法，抓紧的学生，会在头两小时就完成作业，然后看看电视、读读课外书什么的；但也有超过一半的学生会在最后两小时才去做作业，要不是因为没时间，可能还要再拖延下去。
这里做家庭作业这一活动的最早开始时间是四小时的开始，可以理解为 0，而最晚开始时间是两小时之后马上开始，不可以再晚，否则就是延迟了，此时可以理解为 2。显然，当最早和最晚开始时间不相等时就意味着有空闲。
接着，你老妈发现了你拖延的小秘密，于是买了很多的课外习题，要求你四个小时，不许有一丝空闲，省得你拖延或偷懒。此时整个四小时全部被占满，最早开始时间和最晚开始时间都是 0，因此它就是关键活动了。
也就是说，我们只需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。如果不等，则就不是。
为此，我们需要定义如下几个参数。

事件的最早发生时间etv（earliest time of vertex）：即顶点 v $_k$ 的最早发生时间。
事件的最晚发生时间ltv（latest time of vertex）：即顶点 v $_k$ 的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。
活动的最早开工时间ete（earliest time of edge）：即弧 a $_k$ 的最早发生时间。
活动的最晚开工时间Ite（atest time of edge）：即弧 a $_k$ 的最晚发生时间，也就是不推迟工期的最晚开工时间。

我们是由 1 和 2 可以求得 3 和 4，然后再根据ete[k]是否与lte[k]相等来判断 a $_k$ 是否是关键活动。

2.2 关键路径算法

我们将下图的AOE网转化为邻接表结构如下图所示，注意与拓扑排序时邻接表结构不同的地方在于，这里弧链表增加了weight城，用来存储弧的权值。

求事件的最早发生时间etv的过程，就是我们从头至尾找拓扑序列的过程，因此，在求关键路径之前，需要先调用一次拓扑序列算法的代码来计算etv和拓扑序列列表。为此，我们首先在程序开始处声明几个全局变量。

1
2
3

int *etv,*ltv;	/* 事件最早发生时间和最迟发生时间数组 */
int *stack2;	/* 用于存储拓扑序列的栈 */
int top2;		/* 用于stack2的指针 */

其中stack2用来存储拓扑序列，以便后面求关键路径时使用。
下面是改进过的求拓扑序列算法。

/* 拓扑排序 */
Status TopologicalSort(GraphAdjList GL)
{
	EdgeNode *e;
	int i,k,gettop;
	int top=0;		/* 用于栈指针下标 */
	int count=0;	/* 用于统计输出顶点的个数 */
	int *stack;		/* 建栈将入度为0的顶点入栈 */
	stack=(int *)malloc(GL->numVertexes * sizeof(int) ) ;
	for(i = 0; i<GL->numVertexes; i++)
		if(0 == GL->adjList[1].in)
			stack[++top]=i;
	top2=0;		/* ★★★初始化为0 */
	etv=(int *)malloc(GL->numVertexes * sizeof(int) );	/* ★★★事件最早发生时间 */
	for(i=0; i<GL->numVertexes; i++)	/* ★★★ */
		etv[i]=0;	/* ★★★初始化为0 */
	stack2=(int *)malloe(GL->numVertexes * sizeof(int) );	/* ★★★初始化拓扑序列栈 */
	while(top!=0)
	{
		gettop=stack[top--];
		count++;
		stack2[++top2]=gettop;	/* ★★★将弹出的顶点序号压入拓扑序列的栈 */
		for(e = GL->adjList[gettop].firstedge; e; e = e->next )
		{
			k=e->adjvex;
			if( !(--GL->adjList[k].in))
				stack[++top]=k;
			if((etv[gettop] + e->weight) > etv[k])	/* ★★★求各顶点事件最早发生时间值 */
				etv[k] = etv[gettop] + e->weight;	/* ★★★ */
		}
	}
	if (count < GL->numVertexes)
		return ERROR:
	else
		return OK;
}

代码中，除加★★★部分外，与前面讲的拓扑排序算法没有什么不同。
第 12~16 行为初始化全局变量etv数组、top2和stack2的过程。第 22 行就是将本是要输出的拓扑序列压入全局栈stack2中。第 28~29 行很关键，它是求etv数组的每一个元素的值。比如说，假如我们已经求得顶点 v $_0$ 对应的etv[0]=0，顶点 v $_1$ 对应的etv[1]=3，顶点 v $_2$ 对应的etv[2]=4，现在我们需要求顶点 v $_3$ 对应的etv[3]，其实就是求 etv[1]+len<v $_1$ ,v $_3$ > 与 etv[2]+len<v $_2$ ,v $_3$ > 的较大值。显然3+5<4+8, 得到etv[3]=12，如下图所示。在代码中e->weight就是当前弧的长度。

由此我们也可以得出计算顶点 v $_k$ 即求etv[k]的最早发生时间的公式是：

其中P[k]表示所有到达顶点 v $_k$ 的弧的集合。比如上图的P[3]就是 <v $_1$ ,v $_3$ > 和 <v $_2$ ,v $_3$ > 两条弧。len<v $_i$ ,v $_k$ > 是弧<v $_i$ ,v $_k$ >.上的权值。
下面我们来看求关键路径的算法代码。

/* 求关键路径，GL为有向网，输出GL的各项关键活动 */
void CriticalPath(GraphAdjList GL)
{
	EdgeNode te;
	int i,gettop,k,j;
	int ete,lte;	/* 声明活动最早发生时间和最迟发生时间变量 */
	Topologicalsort(GL);	/* 求拓扑序列，计算数组etv和stack2的值 */
	ltv=(int *)malloc(GL->numVertexes*sizeof(int));	/* 事件最晚发生时间 */
	for(i-0; i<GL->numVertexes; i++ )
		ltv[i]=etv[GL->numVertexes-1];	/* 初始化ltv */
	while(top2!=0)		/* 计算Itv */
	{
		gettop=stack2[top2--];
		for (e = GL->adjList[gettop].firstedge; e; e = e->next)
		{ 
			k=e->adjvex:
			if(ltv[k] - e->weight < ltv[gettopl)	/* 求各顶点事件最晚发生时间ltv */
				ltv[gettopl = ltv[k] - e->weight;
			}
		}
	for (j=0; j<GL->numVertexes; j++)	/* 求ete,lte和关键活动 */
	{
		for(e = GL->adjList[j].firstedge; e; e = e->next)
		{
			k=e->adjvex;
			ete = etv[j];	/* 活动最早发生时间 */
			lte = ltv[k] - e->weight;	/* 活动最迟发生时间 */
			if(ete == lte)	/* 两者相等即在关键路径上 */
				printf("<v%d,v%d> length: %d\n", GL->adjList [j].data, GL->adjList[k].data, e->weight);
		}
	}
}

程序开始执行。第 6 行，声明了ete和lte两个活动最早最晚发生时间变量。
第 7 行，调用求拓扑序列的函数。执行完毕后，全局变量数组etv和栈stack2的值如下图所示，top2=10。也就是说，对于每个事件的最早发生时间，我们已经计算出来了。
第 8~10 行为初始化全局变量ltv数组，因为ety[9]=27，所以数组ltv当前的值为：{27, 2727, 27, 27, 2727, 27, 27, 27}。
第 11~20 行为计算ltv的循环。第 13 行，先将stack2的栈头出栈，由后进先出得到gettop=9。根据邻接表中，v $_9$ 没有弧表，所以第 14~ 19 行循环体未执行。
再次来到第 13 行，gettop=8，在第 14~19 行的循环中，v $_9$ 的弧表只有一条<v $_8$ ,v $_9$ >，第 16 行得到k=9，因为ltv[9]-3<ltv[8]，所以ltv[8]= Itv[9]-3=24，如下图所示。
再次循环，当gettop=7、 5、6时，同理可算出ltv相对应的值为 19、25、13，此时ltv值为：{27, 27, 27, 27, 27, 13, 25, 19, 24, 27}。
当gettop=4时，由邻接表可得到 v $_4$ 有两条弧 <v $_4$ ,v $_6$ >、<v $_4$ ,v $_7$ >, 通过第 14~19 行的循环，可以得到ltv[4]=min(ltv[7]- 4,ltv[6] -9)=min(19-4,25-9)=15，如下图所示。

此时你应该发现，我们在计算ltv时，其实是把拓扑序列倒过来进行的。因此我们可以得出计算顶点 v $_k$ 即求ltv[k]的最晚发生时间的公式是：

其中S[k]表示所有从顶点 v $_k$ 出发的弧的集合。比如上图的S[4]就是 <v $_4$ ,v $_6$ > 和 <v $_4$ ,v $_7$ > 两条弧，len<v $_k$ ,v $_j$ >是弧 <v $_k$ ,v $_j$ > 上的权值。
就这样，当程序执行到第 21 行时，相关变量的值如下图所示，比如etv[1]=3而ltv[1]=7，表示的意思就是如果时间单位是天的话，哪怕 v $_1$ 这个事件在第 7 天才开始，也可以保证整个工程的按期完成，你可以提前 v $_1$ 事件开始时间，但你最早也只能在第 3 天开始。跟我们前面举的例子，是先完成作业再玩还是先玩最后完成作业一个道理。
第 21~32 行是来求另两个变量活动最早开始时间ete和活动最晚开始时间Ite，并对相同下标的它们做比较。两重循环嵌套是对邻接表的顶点和每个顶点的弧表遍历。
当j=0时，从 v $_0$ 点开始，有 <v $_0$ ,v $_2$ > 和 <v $_0$ ,v $_1$ > 两条弧。当k=2时，ete=etv[j]=etv[0]=0。lte=ltv[k]-e->weight=ltv[2]-len<v $_0$ ,v $_2$ >=4-4=0，此时ete=lte，表示弧 <v $_0$ ,v $_2$ > 是关键活动，因此打印。当k=1时，ete=etv[j]=etv[0]=0。lte=tv[k]-e->weight=ltv[1]-len<v $_0$ ,v $_1$ >=7-3=4,此时ete≠Ite，因此 <v $_0$ ,v $_1$ > 并不是关键活动，如下图所示。

这里需要解释一下，ete本来是表示活动 <v $_k$ ,v $_j$ > 的最早开工时间，是针对弧来说的。但只有此弧的弧尾顶点 v $_k$ 的事件发生了，它才可以开始，因此ete=etv[k]。
而Ite表示的是活动 <v $_k$ ,v $_j$ > 的最晚开工时间，但此活动再晚也不能等 v $_j$ 事件发生才开始，而必须要在 v $_j$ 事件之前发生，所以 lte=ltv[j]-len<v $_k$ ,v $_j$ >。就像你晚上 23 点睡觉，你不能说到 23 点才开始做作业，而必须要提前 2 小时，在 21 点开始，才有可能按时完成作业。
所以最终，其实就是判断ete与Ite是否相等，相等意味着活动没有任何空闲，是关键活动，否则就不是。
j=1一直到j=9为止，做法是完全相同的，关键路径打印结果为 “<v $_0$ ,v $_2$ > 4, <v $_2$ ,v $_3$ > 8, <v $_3$ ,v $_4$ > 3, <v $_4$ ,v $_7$ >4, <v $_7$ ,v $_8$ > 5, <v $_8$ ,v $_9$ > 3,”，最终关键路径如下图所示。

分析整个求关键路径的算法，第 7 行是拓扑排序，时间复杂度为 $O(n+e)$ ，第 11~20 行时间复杂度为 $O()n$ ，第 11~20 行时间复杂度为 $O(n+e)$ ，第 21~32 行时间复杂也为 $O(n+e)$ ，根据我们对时间复杂度的定义，所有的常数系数可以忽略，所以最终求关键路径算法的时间复杂度依然是 $O(n+e)$ 。
实践证明，通过这样的算法对于工程的前期工期估算和中期的计划调整都有很大的帮助。不过注意，本例是唯一条关键路径，这并不等于不存在多条关键路径的有向无环图。如果是多条关键路径，则单是提高一条关键路径上的关键活动的速度并不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动的速度。这就像仅仅是有事业的成功，而没有健康的身体以及快乐的生活，是根本谈不上幸福的人生一样，三者缺一不可。

3. 总结

有向无环图时常应用于工程规划中，对于整个工程或系统来说，我们一方面关心的是工程能否顺利进行的问题，通过拓扑排序的方式，我们可以有效地分析出一个有向图是否存在环，如果不存在，那它的拓扑序列是什么？另一方面关心的是整个工程完成所必须的最短时间问题，利用求关键路径的算法，可以得到最短完成工程的工期以及关键的活动有哪些。