今天，小编带着大家来学习图中非常重要的一环，拓扑排序和关键路径！

目录

一. 绪论——实际应用

二. 拓扑排序

（一）.含义

（二）.实现原理

 （三）.代码实现

三. 关键路径

（一）.含义

（二）.实现原理

 （三）.代码实现

首先，我们需要知道的是，拓扑排序是关键路径的基础，正因如此，当我们知道了关键路径在生活中的应用，相信大家也就明白这两个算法的重要性了！

一. 绪论——实际应用

我们以实际生活为例，让大家了解关键路径的应用。

假设现在有一个工程，分为好多个步骤，每个步骤又需要不同的时间来完成，关键路径的作用就是让我们知道这个工程里有哪些步骤是不可替代的，会影响整个工期进行，而那些步骤即便慢一些也没关系，不会影响整个工期的。

二. 拓扑排序

（一）.含义

要了解拓扑排序的含义，我们首先要知道AOV网。AOV网就是不带权值的有向的不带环的网图。

什么是不带环？

上图理解！

 而拓扑排序就是基于AOV网图实现的，大家不要感觉说AOV网图条件太苛刻了，实际上我们的很多工程都是AOV网图，只有实现一个步骤才能进行下一个步骤，例如学习就是就是一个AOV网，我们只有学过c语言后才能学数据结构，才能学数据库以及之后的内容。

拓扑排序就是把所有AOV网中的顶点都单次输出出来。

（二）.实现原理

拓扑排序是基于邻接表实现的。

实现拓扑排序，过程如下：

首先我们需要创建一个栈，用来装入度为0的顶点。

1.计算所有顶点的入度，入度为0的入栈

2.出栈一个顶点a，a的入度为0，把它保存在一个int类型数组topo里。

3.从a开始走到它的下一个顶点b，把b的入度减1，再找一个入度为0的顶点入栈。

4.重复步骤2和步骤3，直到所有的顶点都走过为止。

5.topo数组依次输出就是拓扑排序后的结果

还是那句话，上图理解！

 （三）.代码实现

#define Maxvex 100
typedef char vextype;
typedef int undform;
typedef struct arcnode//边表
{
	int arcnode;//此边节点对应顶点的下标
	struct arcnode* nextarcnode;//下一个此根节点指向的边节点
	int weight;//边的权值
}Arcnode;

typedef struct vexnode//节点表
{
	vextype val;//节点值
	Arcnode* Nextarc;//节点指向的第一个边
}Vexnode[Maxvex], onevexnode;

typedef struct Graph//图
{
	Vexnode vexall;//所有的节点作为一个数组
	int vexnum, arcnum;//节点，边的个数
}Graph;
bool ToPosort(Graph* gp, int * Topo)//拓扑排序
{
	int* indegree = (int*)new int[gp->vexnum];//建立入度数组
	memset(indegree, 0, sizeof(int) * gp->vexnum);
	std::stack<int> st;//建立栈
	for (int i = 0; i < gp->vexnum; i++)//计算所有顶点的入度
	{
		arcnode* node = gp->vexall[i].Nextarc;
		while (node != NULL)
		{
			indegree[node->arcnode]++;
			node = node->nextarcnode;
		}
	}
	for (int i = 0; i < gp->vexnum; i++)//入度为0入栈
	{
		if (indegree[i] == 0)
		{
			st.push(i);
		}
	}
	int size = 0;//判断多少个顶点无环
	int topo_i = 0;
	while (!st.empty())
	{
		int i = st.top();
		st.pop();
		Topo[topo_i++] = i;//顶点入拓扑序列
		size++;
		arcnode* node = gp->vexall[i].Nextarc;
		while (node != NULL)
		{
			--indegree[node->arcnode];
			if (indegree[node->arcnode] == 0)
			{
				st.push(node->arcnode);
			}
			node = node->nextarcnode;
		}
	}
	if (size == gp->vexnum) return true;
	else return false;
}

三. 关键路径

（一）.含义

小编想了好久，决定还是用实例来给大家解释关键路径到底是个什么东西。相信大家看完就能完全理解了！

假设现在有一个工程，分为好多个步骤，每个步骤又需要不同的时间来完成，我们可以用一个带权有向无环图——AOE网来表示，顶点代表步骤，边的权值代表步骤1开始执行到下一步将要开始所需时间。

图来表示就是这样：

例图的意思就是从以顶点1代表的起始步骤到以顶点9代表的终点步骤，该工程可以经过这里头的某些顶点步骤来完成。

由图可知该工程可以经历的路径共有4条，分别是：

①1->2->3->6->8->9   完工时间:1+2+2+4+2=11h

②1->4->5->6->7->9   完工时间:1+1+1+3+1=7h

③1->2->3->6->7->9   完工时间:1+2+2+3+1=9h

④1->4->5->6>8->9    完工时间:1+1+1+4+2=9h

而但每条路径从开工到完成所需的时间是不同的，该工程最短7h完成，最长11h完成，而关键路径就是用来算我们确保工程一定能完成的情况下，该步骤时间的改变一定会影响总工期的时间。

什么意思？

我们以该图为例，最长时间11h就是该工程一定能完成的时间，因为在11h内该工程不管采用那条路径都能完成。

1->2->3->6->8->9就是这里边的关键路径，因为这里边的每一个步骤都没有余量时间，而没有余量时间的步骤就是改变该步骤时间就一定会影响工期的步骤。

余量时间：我们拿3和5步骤为例，3到6是2h，5到6是1h，这说明5到6与3到6相比有1小时的空余，这就是余量时间。3就是没有余量时间，而5就是有余量时间。

关键路径就是这些没有余量时间的步骤所连起来的一条通路。

（二）.实现原理

关键路径的实现是基于拓扑排序的。

其次，我们还需要一个int类型数组etv来存放顶点的最早发生时间， int类型数组ltv来存放顶点的最晚发生时间。小编看来看，我们要是想学好关键路径，必须要彻底清楚什么是最早最晚发生时间。

最早发生时间：该顶点在允许的时间范围内，最早进入下一顶点的时间。

最晚发生时间：该顶点在允许的时间范围内，最晚进入下一顶点的时间。

举个例子：

 以该图为例，关键路径是a->c->e->f，所以对于b->d而言有两种选择：

一是早早完成，歇着，这是最早发生时间，值是1，因为a->b需要1小时；

二是先歇着，等到能和c->e一起完成时再开始，这是最晚发生时间，值是2，因为是a->b加歇的1小时。

我们用拓扑序列topo数组从头开始依次算每个顶点的最早发生时间，因为topo数组是按从图头开始依次存放直到图尾，刚好符合顶点依次发生，所需时间是之前顶点时间的迭代。

再从拓扑序列尾开始往前走，依次计算最晚发生时间，以d点为例，最晚发生时间就是f的最晚时间减d->f的时间，即5-1=4。

所有顶点都算完etv与ltv后，遍历每个顶点，如果一个顶点的最早发生时间etv等于最晚发生ltv时间，那它就是关键路径的顶点。

最后，打印每个关键路径的顶点到下一个关键路径顶点即可。

 （三）.代码实现

void CriticalPath(Graph* gp)//关键路径
{
	cout << "****************CriticalPath*******************\n";
	int* topo = (int*)new int[gp->vexnum];
	if (!ToPosort(gp, topo))//判断是否带环
	{
		cout << "非AOE图！";
		return;
	}
	int* etv = (int*)new int[gp->vexnum];//顶点最早发生时间 
	int* ltv = (int*)new int[gp->vexnum];//顶点最晚发生时间
	for (int i = 0; i < gp->vexnum; i++)//初始化etv
	{
		etv[i] = 0;
	}
	for (int i = 0; i < gp->vexnum; i++)//建立最早时间etv
	{
		arcnode* node = gp->vexall[topo[i]].Nextarc;//拓扑序列中该顶点的第一条边,下标是拓扑序列值，即topo[i]作为下标！
		while (node != NULL)
		{
			if (etv[node->arcnode] < etv[topo[i]] + node->weight)
				//存最早时间，但是最早时间定义是确保事件一定能发生，要想一定能发生，那么就该取时间最长的路径，这就是最早发生时间
				etv[node->arcnode] = etv[topo[i]] + node->weight;
			node = node->nextarcnode;
		}
	}
	for (int i = 0; i < gp->vexnum; i++)//初始化最晚发生时间
	{
		ltv[i] = etv[topo[gp->vexnum - 1]];//注意！这里是用topo序列的值来作为下标的，拓扑序列的尾才是图的尾
	}
	for (int i = gp->vexnum - 1; i >= 0; i--)//建立最晚时间ltv
	{
		arcnode* node = gp->vexall[topo[i]].Nextarc;//从拓扑序列尾端开始,所以用topo[i]来作为下标！
		while (node != NULL)
		{
			if (ltv[topo[i]] > ltv[node->arcnode] - node->weight)
				// 节点顺序关系：  i -> node
				ltv[topo[i]] = ltv[node->arcnode] - node->weight;
			node = node->nextarcnode;
		}
	}
	for (int i = 0; i < gp->vexnum; i++)//判断关键路径并打印
	{
		arcnode* node = gp->vexall[i].Nextarc;
		while (node != NULL)
		{
			if (ltv[node->arcnode] == etv[i] + node->weight)//注意要用最早发生时间加权值来与最晚发生时间相比
				cout << gp->vexall[i].val << "->" << gp->vexall[node->arcnode].val << endl;
			node = node->nextarcnode;
		}
	}
}

创作不易，恳求点赞支持😆 如有错误，敬请斧正

一、 实验目的

理解有向图的基本概念，掌握有向图的存储结构，实现有向图的拓扑排序和关键路径算法.

二、 实验内容

通过编写程序，对示例图进行拓扑排序，进而求解示例图的关键路径。

具体步骤如下：

1. 构造有向带权图；
2. 定义拓扑排序函数判断图中是否存在回路；
3. 定义关键路径求解函数；
4. 主函数实现数据的输入及函数调用。

三、 实验工具

Dev - C++

四、 实验代码

//Authors:xiaobei

#include<stdio.h>
#include<stdlib.h>
#define MVNum 100
#define OK 1
#define ERROR 0
int topo[MVNum];        //定义拓扑排序数组 
//邻接表结构的相关定义
typedef struct ArcNode{       //边表 
 int adjvex;//该边所指向的顶点位置 
 struct ArcNode *nextarc;//指向下一条边的指针 
 char info;    //和边相关信息，权值 
}ArcNode;
typedef struct VNode{       //表头结点表 
 char data;
 ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct{         //邻接表，带权有向图 
 AdjList vertices;
 int vexnum,arcnum;
}ALGraph;
//链栈的相关定义
typedef struct StackLink{
 int data;
 struct StackLink *next;
}StackLink,*StackNode;
int InitStack(StackNode &S){
 S = NULL;
 return OK;
}
int Push(StackNode &S,int e){
 StackNode p;
 p = (StackLink*)malloc(sizeof(StackLink));
 p->data = e;
 p->next = S;
 S = p;
 return OK;
}
int Pop(StackNode &S,int &e){
 StackNode p;
 p = (StackLink*)malloc(sizeof(StackLink));
 if(S==NULL)
  return  ERROR;
 e = S->data;
 p = S;      //用P临时存放栈顶元素，已备释放
 S = S->next; 
 free(p);
 return OK; 
}
int GetTop(StackNode S){
 if(S!=NULL)
  return S->data;
}
int StackEmpty(StackNode S){
 if(S!=NULL)
  return ERROR;
 else 
  return OK;
}
//函数返回顶点所在位置 
int LocateVex(ALGraph G,char c){
 int i;
 for(i=0;i<G.vexnum;++i){
  if(c==G.vertices[i].data)
   return i;
 }
 return -1;
}
//函数用邻接表创建有向无环图 
int CreateDAG(ALGraph &G){
 int i,j,k,weight;
 char v1,v2;
 ArcNode* p;
 printf("\n[请输入总顶点与总边数]:\n>>>");
 scanf("%d %d",&G.vexnum,&G.arcnum);
 for(i=0;i<G.vexnum;i++){         //输入各点，构造表头结点表 
  printf("\n[请依次输入顶点信息]:\n>>>");
  getchar();
  scanf("%c",&G.vertices[i].data);
  G.vertices[i].firstarc = NULL;
 }
 for(k=0;k<G.arcnum;k++){
  printf("\n[请输入各边及权值构造邻接表]:\n>>>");
  getchar();
  scanf("%c %c %d",&v1,&v2,&weight);
  i = LocateVex(G,v1);
  j = LocateVex(G,v2);
  p = (ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex = j;
  p->info = weight;
  p->nextarc = G.vertices[i].firstarc;
  G.vertices[i].firstarc = p;
 }
 return  OK;
}
//函数求出每个顶点入度存入数组 indegree[] 
void FindInDegree(ALGraph G,int indegree[]){
//求有向图邻接表顶点入度,两种方法：1、建立逆邻接表，2、遍历整个邻接表 
//这里采用遍历整个邻接表 
 ArcNode *p;
 int i;
 for(i=0;i<G.vexnum;i++)    //入度初始化为零 
  indegree[i] = 0;
 for(i=0;i<G.vexnum;i++){   //遍历邻接表 
  p = G.vertices[i].firstarc;
  while(p!=NULL){
   indegree[p->adjvex]++;
   p = p->nextarc;
  }
 }
}
//函数获得拓扑排序结果数组topo[] 
int TopologicalSort(ALGraph G,int topo[]){
//有向图G采用邻接表存储结构
//若G无回路，则生成G的一个拓扑序列topo[]并返回OK，否则返回ERROR
 int i;
 ArcNode *p; 
 StackNode S;        //定义链栈 
 int indegree[MVNum];
 FindInDegree(G,indegree);     //求出各顶点入度，存入数组indegree中
 printf("各顶点入度:"); 
 printf("\n-----indegree-----\n");
 for(i=0;i<G.vexnum;i++){
  printf("%d",indegree[i]);
 }
 printf("\n-----indegree-----\n");
 InitStack(S);        //栈初始化为空 
 for(i=0;i<G.vexnum;i++){
  if(indegree[i]==0)
   Push(S,i);       //入度为零者入栈 
 }
 int m=0;
 while(!StackEmpty(S)){
  Pop(S,i);        //将栈顶顶点vi出栈 
  topo[m] = i;       //将vi保存在拓扑序列数组topo中 
  m++;         //对输出顶点计数 
  p=G.vertices[i].firstarc;    //p指向第一个邻接点
  while(p!=NULL){
   int k = p->adjvex;     //vk为vi的邻接点 
   indegree[k]--;      //vi的每个邻接点入度减1 
   if(indegree[k]==0)
    Push(S,k);      //若入度为0则入栈 
   p = p->nextarc;      //p指向vi的下一个邻接点 
  }
 }
 if(m<G.vexnum)        //判断有无回路 
  return ERROR;
 else
  return OK;
}
int CriticalPath(ALGraph G){
//G为邻接表存储的有向网，输出G的各项关键活动
 ArcNode *p;
 int ve[MVNum];     //ve[MVNum]记录每个事件最早发生时间 
 int vl[MVNum];     //vl[MVNum]记录每个事件最迟发生时间 
 int i,j,k,e,l;
 if(!TopologicalSort(G,topo))
  return ERROR;    //调用拓扑排序算法，使拓扑序列保存在topo中；若调用失败，则存在有向环，返回ERROR
 int n = G.vexnum;    //n为顶点个数
 
 for(i=0;i<n;i++)
  ve[i] = 0;     //个每个事件的最早发生时间置初值0
 /*-----------------按拓扑次序求每个事件最早发生时间-----------------*/
 for(i=0;i<n;i++){
  k=topo[i];     //取得拓扑排序序列中顶点序号k 
  p = G.vertices[k].firstarc; //p指向k的第一个邻接顶点 
  while(p!=NULL){    //依次更新k的所有邻接顶点的最早发生时间 
   j = p->adjvex;   //j为邻接顶点的序号 
   if(ve[j]<ve[k]+p->info) //更新顶点j的最早发生时间ve[j] 
    ve[j] = ve[k]+p->info;
   p = p->nextarc;   //p指向k的下一个邻接顶点 
  }
 }
 for(i=0;i<n;i++)    //给每个事件的最迟发生时间置初值ve[n-1] 
  vl[i] = ve[n-1];
 /*-----------------按逆拓扑次序求每个事件最迟发生时间-----------------*/
 for(i=n-1;i>=0;i--){
  k = topo[i];    //取得拓扑排序序列中顶点序号k 
  p = G.vertices[k].firstarc; //p指向k的第一个邻接顶点
  while(p!=NULL){    //根据k的邻接点，更新k的最迟发生时间 
   j = p->adjvex;   //j为邻接顶点的序号 
   if(vl[k]>vl[j]-p->info) //更新顶点k的最早发生时间vl[k] 
    vl[k] = vl[j]-p->info;
   p = p->nextarc;   //p指向k的下一个邻接顶点 
  }
 }
 /*-----------------判断每一活动是否为关键活动-----------------*/
 printf("关键路径如下:\n\n");
 for(i=0;i<n;i++){
  p = G.vertices[i].firstarc; //p指向k的第一个邻接顶点
  while(p!=NULL){
   j = p->adjvex;   //j为i的邻接顶点的序号 
   e = ve[i];    //计算活动<vi,vj>的最早开始时间 
   l = vl[j]-p->info;  //计算活动<vi,vj>的最迟开始时间 
   if(e==l)     //若为关键活动则输出<vi,vj> 
    printf("<%c,%c>",G.vertices[i].data,G.vertices[j].data);
   p = p->nextarc;   //p指向i的下一个邻接顶点 
  } 
 }
 printf("  ->end\n");
 return OK;
}
//菜单函数
void Menu(){
 printf("\n---------菜单-------\n");
 printf("\n1、创建图结构\n");
 printf("\n2、拓扑排序\n");
 printf("\n3、计算关键路径\n");
 printf("\n0、退出\n");
 printf("\n--------------------\n");
 printf("\n[请输入你的选择:]\n>>>");
} 
//主函数 
int main(){
 int i,user;
 ALGraph G;
 while(true){
  Menu();
  scanf("%d",&user);
  switch(user){
   case 1:{
   if(CreateDAG(G))
    printf("\n创建成功……\n");
   break;
   }
   case 2:{
  if(TopologicalSort(G,topo)){
   printf("拓扑排序结果如下:\n\n");
   for(i=0;i<G.vexnum;i++)
    printf("%c->",G.vertices[topo[i]].data);
   printf("end\n");
 }
  break;
   }
   case 3:{
    CriticalPath(G);
    break;
   }
   case 0:exit(0);
  }
 }
 return 0;
}

五、实验结果

1. 创建图结构

2. 拓扑排序

3.关键路径

4.退出

六、总结与思考

1.　用顶点表示活动，用弧表示顶点间的优先关系的有向图，称为顶点表示活动的网，简称（Activity On Vertex Network）AOV-网;

2.　所谓拓扑排序，就是将AOV-网中的所有顶点排成一个线性序列，该序列满足：若在AOV-网中由顶点vi到顶点vj有一条路径，则在该线性序列中，顶点vi必在vj之前;

3.　拓扑排序的过程，重复选择没有直接前驱的顶点;

4.　与AOV-网相对，AOE-网是以边表示活动的网。AOE-网是一个带权的有向无环图。顶点表示事件，弧表示活动，权表示活动持续时间。

5.　AOE-网在工程计划和经营管理中通常需要解决以下两个问题:

1）估算完成整项工程至少需要多长时间；
2）判断哪些活动是影响工程进度的关键；

6.　源点、汇点、关键活动、关键路径

7.　一个活动的最迟开始时间l(i)与最早开始时间e(i)的差值l(i)-e(i)是该活动完成的时间余量，它是在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间，当一个活动时间余量为零时，说明该活动必须如期完成，否则会拖延整个工程进度。所以称l(i)-e(i)=0，即l(i)=e(i)的活动为关键活动。

AOV网：顶点表示活动，弧表示活动间的优先关系的有向图。无有向环。

AOE网：顶点表示事件，弧表示活动，权表示活动持续的时间的有向无环图。

1.拓扑排序（AOV网）

const int MAX_VERTEX_NUM = 20;
//图的邻接表存储：对图的每个顶点建立一个单链表。需要两种类型的节点。一种是表头节点(数量=图的顶点数)，以向量形式存储，以便随机访问任一顶点的链表；
//一种是与表头节点表示的顶点邻接的顶点，链接到相应表头节点后面
//与表头节点表示的顶点邻接的顶点的节点，包括一个顶点的数据域adjvex和一个指向下一个与表头节点邻接的顶点的指针
typedef struct adjNode{
	int adjvex;
	struct adjNode *nextadj;
}adjNode;
//表头节点，包括顶点的数据域和指向第一个与其邻接的顶点的指针
typedef struct VNode {
	int data;
	int indegree = 0;  //入度
	adjNode *firstadj;
}VNode,adjList[MAX_VERTEX_NUM]; //数结构体组存储所有表头结点
//图
typedef struct {
	adjList vertices; //表头节点数组
	int vexnum, arcnum;  //图的顶点数和边数
}Graph;

//建立有向图
//时间复杂度：O(n+e)
void BuildAdjlist(Graph& G,int n,int e) {
	G.vexnum = n;
	G.arcnum = e;
	//先逐个画出图的全部顶点 从1到n编号
	for (int i = 1; i <= n; ++i) {
		G.vertices[i].data = i;
		G.vertices[i].firstadj = NULL;
	}
	for (int i = 0; i < e; ++i) {
		cout << "输入有向边：";
		int u, v;
		cin >> u >> v;
		//表头节点u的邻接表中应加一个顶点v，即插入一个顶点p(插到最前面）
		adjNode *p = new adjNode;
		p->adjvex = v;
		p->nextadj = G.vertices[u].firstadj;
		G.vertices[u].firstadj = p;
		G.vertices[v].indegree++;  //v顶点入度加1
		//delete p;	// 不可delete p!!正在构造链表
	}
}
//拓扑排序
bool toposort(Graph& G,vector<int>& res) {
	stack<int> s;
	for (int i = 1; i <= G.vexnum; ++i) {
		if (G.vertices[i].indegree == 0) {
			s.push(i);
		}
	}
	int count = 0;
	while (!s.empty()) {
		int j = s.top(); s.pop();
		count += 1;
		res.push_back(j);
		adjNode *p = G.vertices[j].firstadj;
		while (p != NULL) {
			int k = p->adjvex;
			G.vertices[k].indegree--;
			if (G.vertices[k].indegree == 0) {
				s.push(k);
			}
			p = p->nextadj;
		}
	}
	if (count < G.vexnum)  return false;  //图中存在有向环
	else return true;
}

//优化空间：用值为0的入度域存放链栈指针以指示下一个入度为0的顶点
bool toposort(Graph& G,vector<int>& res) {
	int top = 0; //指向入度为0的顶点
	for (int i = 1; i <= G.vexnum; ++i) {
		if (G.vertices[i].indegree == 0) {
			G.vertices[i].indegree = top;
			top = i;
		}
	}
	int count = 0;
	while (top!=0) {
		int j = top; 
		top = G.vertices[top].indegree; //相当于退栈
		count += 1;
		res.push_back(j);
		adjNode *p = G.vertices[j].firstadj;
		while (p != NULL) {
			int k = p->adjvex;
			G.vertices[k].indegree--;
			if (G.vertices[k].indegree == 0) {
				G.vertices[k].indegree = top;//新的入度为0的顶点入栈
				top = k;
			}
			p = p->nextadj;
		}
	}
	if (count < G.vexnum)  return false;  //图中存在有向环
	else return true;
}

int main() {
	Graph G;
	int n, e;
	cout<< "输入顶点数和边数：";
	cin >> n >> e;
	BuildAdjlist(G, n, e);
	//打印图的邻接表
	for (int i = 1; i <= n; ++i){
		cout << G.vertices[i].data << "(" << G.vertices[i].indegree << ")";
		if (G.vertices[i].firstadj == NULL) {
			cout << endl;
			continue;
		}
		adjNode* p = G.vertices[i].firstadj;
		while (p != NULL) {
			cout << "->" << p->adjvex;
			p = p->nextadj;
		}
		cout << endl;
	}
	vector<int> res;
	if (toposort(G, res) == true) {
		cout << "拓扑序列为：";
		for (auto& x : res) {
			cout << x << ends;
		}
	}
	else {
		cout << "图中存在有向环！" << endl;
	}
}

分析算法,对有n个顶点和e条弧的有向图而言,建立邻接表的时间复杂度为0(n+e);搜索入度为0的时间复杂度为O( n);在拓扑排序过程中,若有向图无环,则每个顶点进一次栈, 出一次栈,入度减1的操作在WHILE语句中总共执行e次,所以,总的时间复杂度为O(n + e)。上述拓扑排序的算法亦是下节讨论的求关键路径的基础。
当有向图中无环时,也可利用深度优先遍历进行拓扑排序,因为图中无环，则由图中某点出发进行深度优先搜索遍历时,最先退出DFS函数的顶点即出度为零的顶点,是拓扑有序序列中最后一个顶点。由此,按退出DFS函数的先后记录下来的顶点序列(如同求强连通分量时finished数组中的顶点序列)即为逆向的拓扑有序序列。
leetcode课程表

2.关键路径（AOE网)

关键路径: 任务计划作业图上的需要时间最长的路径(可有多条)。它决定完成总任务的时间。

工程的最小时间: 从开始顶点到结束顶点的最长路径的长(该路径上各活动的时间总和)。

用e(i)表示活动 ai 的最早开始时间；在不推迟整个工程完成的前提下，一个活动可以最晚开始的时间定义为该活动的最迟开始时间，用l(i)表示。

用e(i)- l(i)表示活动 ai 的时间余量，即 ai 在不影响总工期的前提下，可以延缓的时间。

e(i)=l(i)的表示活动 ai 称关键活动，显然关键路径上的所有活动都是关键活动，要加快工期只有提速关键活动的速度。

设活动 ai 用弧<j,k>表示，dut(<j,k>)表示权值。
e(i)：活动 ai 的最早开始时间；
l(i)：活动 ai 的最迟开始时间；
Ve(j)：事件 j 的最早发生时间；
Vl(j)：事件 j 的最迟发生时间；
则：e(i)=Ve(j) →演变为计算Ve
l(i)=Vl(k)-dut(<j , k>) →演变为计算求Vl

const int MAX_VERTEX_NUM = 20;
typedef struct adjNode{
	int adjvex;
	int dut;  //活动持续时间
	struct adjNode *nextadj;
}adjNode;
//表头节点，包括顶点的数据域和指向第一个与其邻接的顶点的指针
typedef struct VNode {
	int data;
	int indegree = 0;  //入度
	adjNode *firstadj;
}VNode,adjList[MAX_VERTEX_NUM]; //数结构体组存储所有表头结点
//图
typedef struct {
	adjList vertices; //表头节点数组
	int vexnum, arcnum;  //图的顶点数和边数
}Graph;

//建立有向图
void BuildAdjlist(Graph& G,int n,int e) {
	G.vexnum = n;
	G.arcnum = e;
	//先逐个画出图的全部顶点 从1到n编号
	for (int i = 1; i <= n; ++i) {
		G.vertices[i].data = i;
		G.vertices[i].firstadj = NULL;
	}
	for (int i = 0; i < e; ++i) {
		cout << "输入有向边及权：";  
		int u, v, w;
		cin >> u >> v >>w;
		//表头节点u的邻接表中应加一个顶点v，即插入一个顶点p(插到最前面）
		adjNode *p = new adjNode;
		p->adjvex = v;
		p->dut = w;
		p->nextadj = G.vertices[u].firstadj;
		G.vertices[u].firstadj = p;
		G.vertices[v].indegree++;  //v顶点入度加1
		//delete p;	// 不可delete p!!正在构造链表
	}
}

//在拓扑排序过程中计算各顶点的最早发生时间ve
//优化空间：用值为0的入度域indegree存放链栈指针以指示下一个入度为0的顶点.入度域初始放入度，运行过程可被拓扑栈和逆拓扑栈占用：拓扑出栈时，逆拓扑入栈
void critical_path(Graph& G) {
	vector<int> ve(G.vexnum+1), vl(G.vexnum+1); //事件（顶点）的最早发生时间
	int ftop = 0; //拓扑栈初始化
	int btop = 0; //逆拓扑栈初始化
	//求ve  在拓扑排序过程中计算各顶点的最早发生时间ve
	for (int i = 1; i <= G.vexnum; ++i) {
		if (G.vertices[i].indegree == 0) {
			G.vertices[i].indegree = ftop;
			ftop = i;
			ve[i] = 0;//初始化所有事件（顶点）的最早发生时间为0
		}
	}
	int count = 0;
	while (ftop!=0) {
		int j = ftop; 
		ftop = G.vertices[ftop].indegree; //相当于拓扑退栈
		G.vertices[j].indegree = btop;   btop = j; //逆拓扑入栈
		count += 1;

		adjNode *p = G.vertices[j].firstadj; //p是j的邻接点
		while (p != NULL) {
			int k = p->adjvex; 
			G.vertices[k].indegree--;
			if (G.vertices[k].indegree == 0) {
				G.vertices[k].indegree = ftop; //新的入度为0的顶点入栈
				ftop = k;
			}
			//计算顶点k的ve
			if (ve[k] < ve[j] + p->dut) {
				ve[k] = ve[j] + p->dut;
			}
			p = p->nextadj;
		}
	}
	if (count < G.vexnum) {
		cout << "图中存在有向环!" << endl;
		exit(0);
	}
	
	//求vl
	int endnode = btop; //逆拓扑序列第一个元素编号
	vl[endnode] = ve[endnode];  //初始化顶点事件最迟发生时间
	while (btop != 0) {
		int j = btop;
		btop = G.vertices[btop].indegree;
		vl[j] = ve[endnode];  //vl初始化均为最大值ve(n)
		adjNode* p = G.vertices[j].firstadj;
		while (p != NULL) {
			int k = p->adjvex;
			if (vl[j] > vl[k] - p->dut) {
				vl[j] = vl[k] - p->dut;
			}
			p = p->nextadj;
		}
	}
	//求e(i),l(i)和关键活动
	for (int i = 1; i <= G.vexnum; ++i) {
		adjNode* p = G.vertices[i].firstadj;
		char flag;
		while (p != NULL) {
			int ee = ve[i], el = vl[p->adjvex] - p->dut;
			if (ee == el) flag = '*';
			else flag = ' ';
			cout << "<" << i << "," << p->adjvex << ">" << "," << p->dut << "," << ee <<"="<< el << " " << flag << endl;
			p = p->nextadj;
		}
	}
}

int main() {
	Graph G;
	int n, e;
	cout<< "输入顶点数和边数：";
	cin >> n >> e;
	BuildAdjlist(G, n, e);
	//打印图的邻接表
	for (int i = 1; i <= n; ++i){
		cout << G.vertices[i].data << "(" << G.vertices[i].indegree << ")";
		if (G.vertices[i].firstadj == NULL) {
			cout << endl;
			continue;
		}
		adjNode* p = G.vertices[i].firstadj;
		while (p != NULL) {
			cout << "->" << p->adjvex;
			p = p->nextadj;
		}
		cout << endl;
	}

	critical_path(G);
}