拓扑排序8.68.6.1什么是拓扑排序有向图设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列v1、V2、、Vn称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若是图中的有向边或者从顶点v到顶点v，有一条路径，则在序列中顶点V必须排在顶点V,之前。在一个有向图G中找一个拓扑序列的过程称为拓扑排序。1/29
设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列v1、v2、.、vn 称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若是 图中的有向边或者从顶点vi到顶点vj有一条路径，则在序列中顶点vi必 须排在顶点vj之前。 在一个有向图G中找一个拓扑序列的过程称为拓扑排序。 有向图 1/29
例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业，假设这些课程的名称与相应代号有如下关系：课程代号课程名称先修课程无高等数学C1无C2程序设计C1离散数学C3C4数据结构C2, C3编译原理CsC2, C4Ce操作系统C4, C7C,计算机组成原理C22/29
课程代号 课程名称 先修课程 C1 高等数学 无 C2 程序设计 无 C3 离散数学 C1 C4 数据结构 C2，C3 C5 编译原理 C2，C4 C6 操作系统 C4，C7 C7 计算机组成原理 C2 例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业， 假设这些课程的名称与相应代号有如下关系： 2/29
课程之间的先后关系可用有向图表示：可以这样排课：C,-Cg-Cs-1-C3-C2-C4C2-C7-C1-C3C4-Cs-C6第1学期第2学期3/29
课程之间的先后关系可用有向图表示： C1 C3 C4 C2 C7 C6 C5 可以这样排课： C1-C3-C2-C4- C7-C6-C5 C2-C7-C1-C3- C4-C5-C6 第1学期 第2学期 3/29
拓扑排序的过程如下：（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它。（2）从图中删去该顶点，并且删去从该顶点发出的全部有向边。（3）重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。4/29
（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它。 （2）从图中删去该顶点，并且删去从该顶点发出的全部有向边。 （3）重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。 拓扑排序的过程如下： 4/29
拓扑排序的结果有两种：一种是图中全部顶点都被输出，即得到包含全部顶点的拓扑序列，称为成功的拓扑排序。另一种就是图中顶点未被全部输出，即只能得到部分顶点的拓扑序列，称为失败的拓扑排序。说明有向图中存在回路。5/29
拓扑排序的结果有两种： 一种是图中全部顶点都被输出，即得到包含全部顶点的拓扑序列， 称为成功的拓扑排序。 另一种就是图中顶点未被全部输出，即只能得到部分顶点的拓扑 序列，称为失败的拓扑排序。 说明有向图中存在回路。 5/29
产生一个拓扑序列：福C3C2C7CC排序完成6/29
C1 C3 C4 C2 C7 C6 C5 产生一个拓扑序列： C1 C3 C2 C7 C4 C6 C5 排序完成 6/29
8.6.2拓扑排序算法设计在设计拓扑排序算法时，假设给定的有向图采用邻接表作为存储结构，需要考虑顶点的入度，为此设计一个ind数组，indil存放顶点的入度，先通过邻接表G求出ind。拓扑排序是设计要点如下：在某个时刻，可以有多个入度为0的顶点，为此设置一个栈st，以存放多个入度为0的顶点，栈中的顶点的都是入度为0的顶点。出栈顶点时，将顶点输出，同时删去该顶点的所有出边，实际上没有必要真的删去这些出边，只需要将顶点的所有出边邻接点的入度减1就可以了。7/29
在设计拓扑排序算法时，假设给定的有向图采用邻接表作为存储结构，需 要考虑顶点的入度，为此设计一个ind数组，ind[i]存放顶点i的入度，先通 过邻接表G求出ind。拓扑排序是设计要点如下： 在某个时刻，可以有多个入度为0的顶点，为此设置一个栈st，以存 放多个入度为0的顶点，栈中的顶点的都是入度为0的顶点。 出栈顶点i时，将顶点i输出，同时删去该顶点的所有出边，实际上 没有必要真的删去这些出边，只需要将顶点i的所有出边邻接点的入 度减1就可以了。 7/29
1/拓扑排序public static void TopSort(AdjGraphclass G)1/记录每个顶点的入度( int[] ind=new int[MAxV];//初始化ind数组Arrays.fill(ind,o);ArcNode p;1/求顶点i的入度for（inti=o;i，顶点j的入度增1p=p.nextarc;1/定义一个栈Stackst=new Stack();1/所有入度为0的顶点进栈for (int i=o;i<G.n;i++)if (ind[i]==0)st.push(i);8/29
public static void TopSort(AdjGraphClass G) //拓扑排序 { int[] ind=new int[MAXV]; //记录每个顶点的入度 Arrays.fill(ind,0); //初始化ind数组 ArcNode p; for (int i=0;i，顶点j的入度增1 p=p.nextarc; } } Stack st=new Stack(); //定义一个栈 for (int i=0;i<G.n;i++) //所有入度为0的顶点进栈 if (ind[i]==0) st.push(i); 8/29
1/栈不为空时循环while(!st.empty())1/出栈一个顶点1(int i=st.pop();1/输出顶点1System.out.print(i+"");1/找第一个邻接点p=G.adjlist[i].firstarc;while (p!=null) int j=p.adjvex;ind[j]--;1/顶点j的入度减1if(ind[j]==0)11入度为0的邻接点进栈st.push(j);1/找下一个邻接点p=p.nextarc;7不考虑求初始入度，时间复杂度为o(n+e)9/29
while (!st.empty()) //栈不为空时循环 { int i=st.pop(); //出栈一个顶点i System.out.print(i+" "); //输出顶点i p=G.adjlist[i].firstarc; //找第一个邻接点 while (p!=null) { int j=p.adjvex; ind[j]-; //顶点j的入度减1 if (ind[j]==0) //入度为0的邻接点进栈 st.push(j); p=p.nextarc; //找下一个邻接点 } } } 不考虑求初始入度，时间复杂度为O(n+e)。 i j . 9/29
8.7AOE网与关键路径8.7.1什么是AOE网和关键路径若用一个带权有向图（DAG）描述工程的预计进度，以顶点表示事件，有向边表示活动，边e的权c（e)表示完成活动e所需的时间（比如天数），或者说活动e持续时间AOE网。通常AOE网中只有一个入度为0的顶点，称为源点，和一个出度为0的顶点称为汇点。在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。完成整个工程的最短时间就是网中关键路径的长度。关键路径上的活动称为关键活动，或者说关键路径是由关键活动构成的。只要找出AOE网中的全部关键活动，也就找到了全部关键路径了。18/29
若用一个带权有向图（DAG）描述工程的预计进度，以顶点表示事件，有 向边表示活动，边e的权c(e)表示完成活动e所需的时间（比如天数）， 或者说活动e持续时间 AOE网。 通常AOE网中只有一个入度为0的顶点，称为源点，和一个出度为0的顶点， 称为汇点。 在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为 关键路径。完成整个工程的最短时间就是网中关键路径的长度。 关键路径上的活动称为关键活动，或者说关键路径是由关键活动构成的。 只要找出AOE网中的全部关键活动，也就找到了全部关键路径了。 10/29