河池学院：《数据结构》课程电子教案（PPT教学课件）第8章 图 8.6 拓扑排序 8.7 AOE网与关键路径

设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列v1、v2、.、vn 称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若是 图中的有向边或者从顶点vi到顶点vj有一条路径，则在序列中顶点vi必 须排在顶点vj之前。 在一个有向图G中找一个拓扑序列的过程称为拓扑排序。 有向图 1/29

课程代号 课程名称 先修课程 C1 高等数学 无 C2 程序设计 无 C3 离散数学 C1 C4 数据结构 C2，C3 C5 编译原理 C2，C4 C6 操作系统 C4，C7 C7 计算机组成原理 C2 例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业， 假设这些课程的名称与相应代号有如下关系： 2/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

拓扑排序的结果有两种： 一种是图中全部顶点都被输出，即得到包含全部顶点的拓扑序列， 称为成功的拓扑排序。 另一种就是图中顶点未被全部输出，即只能得到部分顶点的拓扑 序列，称为失败的拓扑排序。 说明有向图中存在回路。 5/29

C1 C3 C4 C2 C7 C6 C5 产生一个拓扑序列： C1 C3 C2 C7 C4 C6 C5 排序完成 6/29

在设计拓扑排序算法时，假设给定的有向图采用邻接表作为存储结构，需 要考虑顶点的入度，为此设计一个ind数组，ind[i]存放顶点i的入度，先通 过邻接表G求出ind。拓扑排序是设计要点如下： 在某个时刻，可以有多个入度为0的顶点，为此设置一个栈st，以存 放多个入度为0的顶点，栈中的顶点的都是入度为0的顶点。 出栈顶点i时，将顶点i输出，同时删去该顶点的所有出边，实际上 没有必要真的删去这些出边，只需要将顶点i的所有出边邻接点的入 度减1就可以了。 7/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

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

若用一个带权有向图（DAG）描述工程的预计进度，以顶点表示事件，有 向边表示活动，边e的权c(e)表示完成活动e所需的时间（比如天数）， 或者说活动e持续时间  AOE网。 通常AOE网中只有一个入度为0的顶点，称为源点，和一个出度为0的顶点， 称为汇点。 在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为 关键路径。完成整个工程的最短时间就是网中关键路径的长度。 关键路径上的活动称为关键活动，或者说关键路径是由关键活动构成的。 只要找出AOE网中的全部关键活动，也就找到了全部关键路径了。 10/29