拓扑排序

拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。举例：计算机专业的学生应该学习的部分课程及其每门课程所需要的先修课程。拓扑排序的方法：（1）从图中选择一个入度为0的顶点且输出之；（2）从图中删掉该顶点及其所有以该顶点为弧尾的弧；反复执行这两个步骤，直到所有的顶点都被输出，输出的序列就是这个无环有向图的拓扑序列。细心的读者可能会发现：在每一时刻，可能同时存在多个入度为0的顶点，选择注：表中c1~c9列表示的是每个顶点的入度。下面我们讨论一下如何实现拓扑排序的算法。假设有向图以邻接表的形式存储。下面给出算法实现的基本过程：{ 将所有入度为0的顶点入栈；当栈非空时重复执行下列操作：从栈中退出顶点k；（1）将k顶点的信息输出；（2）将与k邻接的所有顶点的入度减1。 }#defineMAX_VERTEX_NUM30//最大顶点个数typestructEdgeLinklist{//边结点intadjvex;structEdgeLinklist*next;}EdgeLinklist;typedefstructVexLinklist{//顶点结点Elemtypeelem;intindegree;//记录顶点的入度EdgeLinklist*firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];下面是拓扑排序的完整算法。 StatusTopologicalSort(AdjListadj){InitStack(s);for(i=0;i<MAX_VERTEX_NUM-1;i++)if(adj.indegree==0)Push(s,i);while(!StackEmpty(s)){Pop(s,i);printf(i);for(p=adj.firstedge;p;p=p->next){adj.indegree-=1;if(adj.indegree==0)Push(s,i);}

给定一个n个点m条边的有向图，点的编号是1到n，图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。 若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。 输入格式 第一行包含两个整数n和m 接下来m行，每行包含两个整数x和y，表示存在一条从点x到点y的有向边(x, y)。 输出格式 共一行，如果存在拓扑序列，则输出拓扑序列。 否则输出-1。 数据范围 1≤n,m≤105 拓扑排序：找到没有前驱的结点，删除。重复这个步骤。最后按照删除结点的顺序依次输出。 算法框架可以用宽搜，在宽搜框架中加入拓扑排序。

广度优先搜索是最简单的图搜索算法之一。之所以得名是因为该算法始终将已经发现的结点集合，沿着其 广度方向 向外扩展去寻找未发现结点。 具体算法执行过程如下图所示： 深度优先搜索，只有可能就在图中尽可能的 深入 ，总是从最近才发现的结点出发，寻找下一个结点。 具体算法执行过程如下图所示： 拓扑排序是计算机中经常遇到的概念，下面用于《算法导论》的定义 如下图3-1所示，事件E1完成之后，可以同时执行事件E2和E3，两事件执行结束之后，执行事件E4，最后可以同时执行事件E5和E6。每个事件的执行都依赖于它之前事件是否执行完成，执行的顺序是固定的，这样的线性顺序就是 拓扑排序 。 图的广度、深度优先搜索和拓扑排序是图论算法中的基础，也是实践中经常遇到的问题。在考研和面试笔试中会通过选择题或者填空题考察，学习理解上文图示中的算法思想，辅助练习问题不大。当然也有关于这里的算法题，例如LeetCode815公交路线问题，就是利用图的广度优先搜索求解，因为解题复杂，并且在平时的应试中出现概率不大，这里不做详细讲解。有兴趣的可以在LeetCode中搜索，题目后面有我提交过的题解。

有向无环图DAG 顶点表示活动的网络AOV网：用DAG图表示一个工程，其顶点表示活动，有向边<vi,vj>表示活动vi必须先于活动vj进行 拓扑排序（由一个有向无环图的顶点组成的序列） 1.每个顶点出现且仅出现一次 2.若顶点A在序列中排在顶点B之前，则图中不存在B到A的路径 每个DAG图都有一个或多个拓扑排序序列。 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序序列中，每个顶点有唯一的前驱后继关系，再做拓扑排序时，则排序结果是唯一的。 若邻接矩阵是三角矩阵的话拓扑排序一定存在，反之不一定。 步骤 1.从DAG图中选择一个没有前驱的顶点并输出（必须在它之前进行大的活动已经都完成了） 2.从图中删除该顶点和所有以它为起点的有向边 3.重复1，2直到当前的DAG图为空或当前图中不存在无前驱的结点为止。后者说明有环。 栈 时间复杂度O(|V|+|E|) 用深度优先遍历也可以实现拓扑排序 若已知无环图，则可用拓扑排序来改进Dijkstra算法 以拓扑顺序来选取顶点，运行时间为O(|E|+|V|) 用边表示活动的网络AOE网：在带权有向图中，以顶点表示事件，有向边表示活动，以边上的权值表示完成该活动的开销。 1.只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。 2.只有在进入某一顶点的各有向边所代表的活动都已结束，该顶点所代表的事件才能发生。 仅有一个入度为0的顶点，称为开始顶点（源点），表示整个工程的开始。仅有一个出度为0的顶点，结束结点（汇点），表示整个工程的结束。 有些活动是可以并行进行的 从源点都汇点的路径可能有多条，所有路径上的活动都完成了整个工程才算结束，所以把路径长度最大的称为 关键路径 ，其上的活动称为 关键活动 。完成整个工程的最短时间就是关键路径的长度。关键活动不能按时完成，则整个工程的完成时间都会受到影响。 事件Vk的最早发生时间Ve(k) 从开始顶点V到Vk的最长路径长度 Ve(V)=0 Ve(k)=Max{Ve(j)+Weight(Vj, Vk)} 从前往后计算 事件Vk的最迟发生时间Vl(k) 在不推迟整个工程完成的前提下，即保证它所指向的时间Vi在Ve(i)时刻能够发生时，该事件最迟必须发生的时间。 Vl(汇点)=Ve(汇点) Vl(j)=Min{Vl(k)-Weight(Vj, vk)} 从后往前计算 活动Ai的最早开始时间E(i) 等于该活动的起点所表示的事件的最早发生时间 活动Ai的最迟开始时间L(i) 等于该活动的终点所表示的事件的最迟发生时间减去该活动所需要的时间 活动Ai可以拖延的时间D(i) 其最早开始时间与最迟开始时间的差值 若为0的话，就代表该活动必须要如期完成，否则会拖延完成整个工程的进度，则该活动是关键活动。

拓扑排序（Topological Sorting） 拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。 DAG的判定 拓扑排序的时间复杂度为O ( V + E ),因为DFS的时间复杂度度为O ( V + E ) 该序列必须满足下面两个条件： 它是一个 DAG 图，那么如何写出它的拓扑排序呢？这里说一种比较常用的方法： 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。 于是，得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。 通常，一个有向无环图可以有一个或多个拓扑排序序列。 还有一种直观的方法是利用DFS,容易知道拓扑排序的序列为所有顶点的逆后续排列(ReversePostOrder)

拓扑排序(Topological Sort)对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。注意：①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。②若图中存在有向环，则不可能使顶点满足拓扑次序。③一个DAG的拓扑序列通常表示某种方案切实可行。【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。④一个DAG可能有多个拓扑序列。【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。⑤当有向图中存在有向环时，拓扑序列不存在【例】下面(a)图中的有向环重排后如(b)所示，有向边<v3，vl>和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。无前趋的顶点优先的拓扑排序方法该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为：NonPreFirstTopSort(G){//优先输出无前趋的顶点while(G中有人度为0的顶点)do{从G中选择一个人度为0的顶点v且输出之；从G中删去v及其所有出边；}if(输出的顶点数目<|V(G)|)//若此条件不成立，则表示所有顶点均已输出，排序成功。Error("G中存在有向环，排序失败！")；}对G9执行上述算法的执行过程【参见动画演示】和得到的拓扑序列是C0，C1，C2，C4，C3，C5，C7，C9，C6。注意：无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的人度，可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点：在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。