产生一个拓扑序列：福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<G.n;i++)(p=G.adjlist[i].firstarc;while(p!=null){ int j=p.adjvex;ind[j]++;//有边<i,j>，顶点j的入度增1p=p.nextarc;1/定义一个栈Stack<Integer>st=new Stack<Integer>();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<G.n;i++) //求顶点i的入度 { p=G.adjlist[i].firstarc; while (p!=null) { int j=p.adjvex; ind[j]++; //有边<i,j>，顶点j的入度增1 p=p.nextarc; } } Stack<Integer> st=new Stack<Integer>(); //定义一个栈 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