拓扑排序和关键路径是基于无环的有向图。

主要用来表示工程进度中各个事件之间的关系。

 拓扑排序和关键路径 使用邻接表存储数据，最小生成树和最短路径用 邻接矩阵 存储数据。

1、拓扑排序

AOV网：在一个表示工程的有向图中，用固定点表示活动，用弧表示活动之间的优先级关系，这样的有向图为顶点表示活动的网，我们称之为AOV网（Activity On Vertex Network）

拓扑排序：是将一个AOV网的各个顶点按一定顺序排列，要求满足若存在<Vi，Vj>，则排序中的顶点Vi必在顶点Vj之前。对于同一幅图，拓扑排序可有多个拓扑排序。

在显示生活中，用到的拓扑排序的例子：

        学校课程布置图，要先修完一些基础课，才可以继续修专业课，以计算机软件专业为例，在《程序设计基础》和《离散数学》课程学完之前就不能开始学习《数据结构》，这些先决条件定义了课程之间的优先（领先）关系。

算法：

（1）从有向图中选择一个无前驱（入度为0）的顶点输出。

（2）删除此顶点，并删除已此顶点为为尾的弧。

（3）重复（1），（2）步骤，知道输出全部顶点或者AOV网中不存在入度为0的顶点。

具体实现代码：

    用栈来保存入度为0的顶点，和更新后入度为0的顶点

#include 
     
      #define MAXVEX 100typedef struct EdgeNode   /*边表节点*/{int adjvex;       /*邻接点域，存储该顶点对应的下表*/int weight;       /*用于存储权值，对于非网图可以不需要*/struct EdgeNode *next;  /*链域，指向下一个邻节点*/}EdgeNode;typedef struct VertexNode   /*顶点表节点*/{int in;          /*顶点入度*/int data;       /*顶点域，存储顶点信心*/EdgeNode *firstedge; /*边表头指针*/}VertexNode, Adjlist[MAXVEX];typedef struct{Adjlist adjList;int numVertexes;int numEdges;  /*图中当前顶点数和边数*/}graphAdjList, *GraphAdjList;/*拓扑排序，若GL无回路，则输出拓扑排序序列并返回OK，若有回路返回ERROR*/int 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));  //动态分配内存，大小为n个顶点(最多有n个顶点入度为0，因为图总共有n个顶点)for(i = 0; i
      
       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[gettop].firstedge; e！; e=e->next){ /*对此顶点弧表遍历*/k = e->adjvex;if(--GL->adjList[k].in == 0)  //将k号顶点邻接点的入度减1,且减1后，入度为0的顶点需要存到栈中stack[++top] = k;}}if(count < GL->numVertexes)  /*如果count小于顶点数，说明存在环*/return -1;elsereturn 0;}
      
     

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

2、关键路径

拓扑排序是解决一个工程能否顺序进行的问题，但有时还需解决工程完成需要的最短时间。

AOE网：在一个表示工程带权的有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种用有向图的边表示活动的网，我们称之为AOE网（Activity On Edge Network）

用ve(i)表示事件（即顶点)i的最早开始时间，用vl(i)表示事件i的最开始时间，如果活动k由弧<m,n>表示，用dut(<m,n>)表示活动的持续时间，则有：

e(k) = ve(m)

l(k) = vl(n) - dut(<m,n>)

求解关键路径的具体算法（假设图中有n个顶点)

(1) 从开始顶点V0出发，假设ve(0)=0，然后按照拓扑有序求出其他各顶点i的最早开始时间ve(i)，如果得到拓扑序列中顶点数目小于图中的顶点数，则表示图中存在回路，算法结束，否则继续执行。

（2）从结束顶点Vn出发，假设vl(n-1) = ve(n-1);然后求出各顶点i的最晚发生时间。

（3）根据顶点的最早发生时间，和最晚发生时间，依次求出出每条弧的最早开始时间和最晚开始时间，如果两只相等，则为关键活动。关键活动组成的路径则为关键路径。

具体实现代码：

#include 
     
      #define MAXVEX 100/*首先声明几个全局变量*/int *etv,*ltv;  /*时间的最早发生时间和最迟发生时间*/int *stack2;  /*用于存储拓扑序列的栈*/int top2;    /*用于stack2的指针*/typedef struct EdgeNode   /*边表节点*/{int adjvex;       /*邻接点域，存储该顶点对应的下表*/int weight;       /*用于存储权值，对于非网图可以不需要*/struct EdgeNode *next;  /*链域，指向下一个邻节点*/}EdgeNode;typedef struct VertexNode   /*顶点表节点*/{int in;          /*顶点入度*/int data;       /*顶点域，存储顶点信心*/EdgeNode *firstedge; /*边表头指针*/}VertexNode, Adjlist[MAXVEX];typedef struct{Adjlist adjList;int numVertexes;int numEdges;  /*图中当前顶点数和边数*/}graphAdjList, *GraphAdjList;/*拓扑排序，若GL无回路，则输出拓扑排序序列并返回OK，若有回路返回ERROR*/int 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));  //动态分配内存，大小为n个顶点(最多有n个顶点入度为0，因为图总共有n个顶点)for(i = 0; i
      
       numVertexes; i++)if(GL->adjList[i].in == 0)  /*将入度为0的顶点入栈*/stack[++top] = i;top2 = 0;etv = (int*) malloc(GL->numVertexes*sizeof(int));  /*事件的最早发生时间*/for(i=0;i
       
        numVertexes; i++)etv[i] = 0;stack2 = (int*) malloc(GL->numVertexes*sizeof(int)); /*初始化*/while(top != 0){gettop = stack[top--];  /*出栈*/printf("%d -> ",GL->adjList[gettop].data); /*打印此顶点*/stack2[++top2] = gettop;  /*将弹出的顶点序列号压入拓扑序列的栈中*/count++; /*统计输出顶点数*/for(e=GL->adjList[gettop].firstedge; e; e=e->next){ /*对此顶点弧表遍历*/k = e->adjvex;if(--GL->adjList[k].in == 0)  //将k号顶点邻接点的入度减1,且减1后，入度为0的顶点需要存到栈中stack[++top] = k;if((etv[gettop]+e->weight)>etv[k]) /*求各顶点时间最早发生时间*/etv[k] = etv[gettop] + e->weight;  /*某个顶点的最早发生时间= 和他相关的活动必须全部完成*/}}if(count < GL->numVertexes)  /*如果count小于顶点数，说明存在环*/return -1;elsereturn 0;}/*求关键路径，GL为有向网，输出GL的各项关键活动*/void CriticalPath(GraphAdjList GL){EdgeNode *e;int i,gettop,k,j;int ete,lte;    /*声明活动最早发生时间和最迟发生时间*/TopoLogicalSort(GL);  /*求拓扑序列，计算数组etv和stack2的值*/ltv = (int*) malloc(GL->numVertexes*sizeof(int)); /*时间的最晚发生时间*/for(i= 0; i
        
         numVertexes;i++)ltv[i]=etv[GL->numVertexes-1];  /*初始化ltv[i] 为工程完成的最早时间，etv[i]初始化为0*/while(top2!=0)  /*计算ltv*/{gettop = stack2[top2--];for(e=GL->adjList[gettop].firstedge;e!=NUll;e=e->next){/*求各定点事件的最迟发生时间ltv值*/k=e->adjvex;if(ltv[k]-e->weight
         
          weight;   /*求最晚发生时间，是从拓扑序列的最后一个顶点逆着推导*/}}for(j=0;j
          
           numVertexes;j++) /*求关键活动*/{for(e=GL->adjList[j].firstedge;e!=NULL;e=e->next){k=e->adjvex;ete = etv[j]; /*活动最早开始时间*/lte = ltv[k] - e->weight;/*活动最晚发生时间*/if(ete ==lte)printf("
           
             length: %d, ",GL->adjList[j].data,GL->adjList[k].data,e->weight);}}}