拓扑排序

拓扑排序拓扑排序是一种对有向无环图（DAG）进行排序的算法，它可以将图中的节点按照一定的顺序进行排列。

拓扑排序算法常用于任务调度、依赖关系分析等领域。

拓扑排序的基本原理是通过深度优先搜索（DFS）来遍历图中的节点，并根据节点的访问顺序进行排序。

在DFS过程中，首先从某个节点出发，沿着一条路径一直访问下去，直到无法继续访问为止。

然后回溯到上一个节点，继续访问未被访问过的邻接节点。

这样不断地递归下去，直到所有节点都被访问过为止。

拓扑排序算法的基本步骤如下：1.创建一个空的结果列表，用于存储排序后的节点。

2.选择一个未被访问过的节点作为起始节点。

3.从起始节点开始进行DFS遍历，将访问到的节点标记为已访问。

4.在DFS遍历过程中，如果遇到某个节点的所有邻接节点都已经被访问过，则将该节点加入结果列表。

5.继续选择下一个未被访问过的节点作为起始节点，重复步骤3和步骤4，直到所有节点都被访问过。

6.返回结果列表，即为拓扑排序的结果。

下面通过一个具体的例子来说明拓扑排序的原理。

假设有如下的有向无环图（DAG）：A ->B -> C| |v vD -> E首先选择一个未被访问过的节点作为起始节点，假设选择节点A。

从节点A开始进行DFS遍历，首先访问节点A，并将其标记为已访问。

接下来访问节点A的邻接节点B，然后继续访问节点B的邻接节点C。

由于节点C没有邻接节点，所以将节点C加入结果列表，并回溯到节点B。

接着访问节点B的另一个邻接节点E，将节点E 加入结果列表。

然后回溯到节点A，继续访问节点A的另一个邻接节点D，将节点D加入结果列表。

最后回溯到节点A，节点A的所有邻接节点都已经被访问过，将节点A加入结果列表。

此时，结果列表中的节点顺序为C、E、D、A。

但是根据拓扑排序的定义，结果列表应该是一个满足所有依赖关系的顺序。

在这个例子中，节点B依赖于节点A，所以节点B应该在节点A之后。

为了达到这个目的，可以将结果列表中的节点顺序反转，得到最终的拓扑排序结果为A、D、E、C、B。

拓扑排序例子-回复什么是拓扑排序？为什么要进行拓扑排序？如何进行拓扑排序？这篇文章将为你逐步解答这些问题。

拓扑排序是一种用于有向无环图（DAG）的算法，它将图中的节点按照一种特定的顺序进行排序。

拓扑排序往往用于解决有依赖关系的任务调度问题，其中任务的执行必须按照一定的顺序。

通过拓扑排序，我们可以确定任务的执行顺序，确保每个任务在它所依赖的任务执行完毕之后再执行。

那么为什么要进行拓扑排序呢？想象一下，你要为一本书编写目录，你希望按照章节的顺序来编写目录，否则读者可能会迷失在无序的章节中。

在这个例子中，每个章节都相当于一个任务，它们之间存在一定的依赖关系，因为后续的章节可能会引用之前的内容。

通过拓扑排序，你可以确定每个章节的先后顺序，确保目录的编写顺利进行。

那么如何进行拓扑排序呢？拓扑排序使用了一种叫做“深度优先搜索”的算法。

算法从一个未访问的节点开始遍历图，当遍历到一个节点时，它将其标记为已访问，并继续遍历该节点的所有邻接节点。

当一个节点的所有邻接节点都被访问完毕后，它将被添加到排序结果的头部。

最终，我们得到的排序结果就是拓扑排序的结果。

下面，我们来举一个具体的例子来演示拓扑排序的过程。

假设我们有以下的任务依赖关系图：[1] > [2] > [4]\\ v> [3] > [5]在这个图中，节点表示任务，箭头表示任务之间的依赖关系。

例如，节点2依赖于节点1，节点4依赖于节点2，等等。

我们的目标是按照依赖关系的顺序对节点进行排序。

首先，我们从一个未访问的节点开始，假设我们选择节点1。

我们接下来需要遍历节点1的所有邻接节点，即节点2和节点3。

然后，我们继续遍历这两个节点的邻接节点，依次为节点4和节点5。

由于节点4和节点5都没有邻接节点，它们被添加到排序结果的头部。

接着，我们回溯到节点2，它的邻接节点3已经被访问过了，所以它也被添加到排序结果的头部。

最后，我们回溯到节点1，将其添加到排序结果的头部。

什么是拓扑排序？
拓扑排序是一种对有向无环图（DAG）进行排序的算法，它可以将图中的顶点
按照一定的顺序排列，使得图中任意一条边的起点在排列中都出现在终点之前。

具体来说，拓扑排序的过程是这样的：
1. 首先，找到图中入度为0的顶点（即没有任何边指向它的顶点），将其加入到排序的结果中。

2. 然后，移除这个顶点以及由它出发的所有边，更新剩余顶点的入度。

3. 重复以上步骤，直到所有的顶点都被加入到排序结果中或者发现图中存在环。

如果最终所有的顶点都被加入到排序结果中，那么这个排序就是图的一个拓扑
排序；如果在过程中发现了环，那么图不具有拓扑排序。

拓扑排序的应用非常广泛，比如在软件工程中可以用来解决模块的依赖关系，
或者在任务调度中确定任务的执行顺序等等。

这个算法的时间复杂度为O(V+E)，其中V为顶点的数量，E为边的数量。

图基本算法拓扑排序（基于dfs） 拓扑排序，是对有向⽆回路图进⾏排序，以期找到⼀个线性序列，这个线性序列在⽣活正可以表⽰某些事情完成的相应顺序。

如果说所求的图有回路的话，则不可能找到这个序列。

在⼤学数据结构课上，我们知道求拓扑排序的⼀种⽅法。

⾸先⽤⼀个⼊度数组保存每个顶点的⼊度。

在进⾏拓扑排序时，我们需要找到⼊度为0的点，将其存⼊线性序列中，再将其从图中删除（与它相关的边都删除，相邻的顶点的⼊度均减1），再重复上⾯的操作，直⾄所有的顶点都被找到为⽌。

如果不对每次找⼊度为0的顶点的⽅法进⾏处理，⽽直接去遍历⼊度数组，则该算法的时间复杂度为O(|V|2)，如果使⽤⼀个队列来保存⼊度为0的顶点，则可以将这个算法的复杂度降为O(V+E)。

今天在算法导论上看了⽤dfs来求拓扑排序的算法，才发现其⾼深之处，膜拜之Orz…下⾯是算法导论的叙述： 本节说明了如何运⽤深度优先搜索，对⼀个有向⽆回路图（dag）进⾏拓扑排序。

对有向⽆回路图G=(V,E)进⾏拓扑排序后，结果为该图顶点的⼀个线性序列，满⾜如果G包含边（u, v），则在该序列中，u就出现在v的前⾯（如果图是有回路的，就不可能存在这样的线性序列）。

⼀个图的拓扑排序可以看成是图中所有顶点沿⽔平线排列⽽成的⼀个序列。

使得所有的有向边均从左指向右。

因此，拓扑排序不同于通常意义上的排序。

在很多应⽤中，有向⽆回路图⽤于说明时间发⽣的先后次序，下图1即给出⼀个实例，说明Bumstead教授早晨穿⾐的过程。

他必须先穿好某些⾐服，才能再穿其他⾐服（如先穿袜⼦后穿鞋），其他⼀些⾐服则可以按任意次序穿戴（如袜⼦和裤⼦），在图1中，有向边<u，v>表⽰⾐服u必须先于⾐服v穿戴。

因此，该图的拓扑排序给出了⼀个穿⾐的顺序。

图2说明了对该图进⾏拓扑排序后，将沿⽔平线⽅向形成⼀个顶点序列，使得图中所有有向边均从左指向右。

拓扑排序算法具体步骤如下：1、调⽤dfs_travel()；2、在dfs_travel()每次调⽤dfs()的过程中，都记录了顶点s的完成时间，将顶点s按完成顺序保存在存放拓扑排序顺序的数组topoSort[]中。

拓扑排序应用场景拓扑排序是一种常用的图算法，用于解决一些特定的应用场景。

它的主要作用是对有向无环图（DAG）中的节点进行排序，使得所有的边从前向后指向排列的顺序。

在实际应用中，拓扑排序被广泛应用于任务调度、依赖关系分析、编译优化等领域。

在任务调度中，拓扑排序可以用来确定任务的执行顺序。

假设有一组任务，每个任务都有一些依赖关系，即某些任务必须在其他任务执行之后才能开始。

这时候，我们可以将任务看作图中的节点，依赖关系看作图中的边，利用拓扑排序算法确定任务的执行顺序。

通过拓扑排序，我们可以确保没有任务在其依赖任务执行之前开始，从而保证任务的正确执行。

拓扑排序也可以应用于依赖关系分析。

在软件开发中，各个模块之间可能存在依赖关系，即某些模块需要依赖其他模块的输出结果才能正常工作。

通过使用拓扑排序，可以分析模块之间的依赖关系，找出模块之间的依赖顺序，从而保证软件的正确运行。

另一个应用场景是编译优化。

在编译过程中，源代码会经过多个阶段的处理，例如词法分析、语法分析、语义分析等。

这些处理过程之间也存在依赖关系，必须按照一定的顺序进行。

通过拓扑排序，可以确定编译过程中各个阶段的执行顺序，从而提高编译的效率和准确性。

除了上述应用场景，拓扑排序还可以用于解决其他问题。

例如，可以用拓扑排序来判断一个有向图是否存在环路，如果拓扑排序中存在环路，则图中存在环路；反之，如果拓扑排序中不存在环路，则图中不存在环路。

此外，拓扑排序还可以用于确定关键路径，即在一组任务中找出耗时最长的路径，从而可以优化任务的执行时间。

拓扑排序是一种非常实用的图算法，广泛应用于任务调度、依赖关系分析、编译优化等领域。

通过拓扑排序，可以确定任务的执行顺序，分析模块之间的依赖关系，优化编译过程，判断图中是否存在环路，确定关键路径等。

这些应用场景都可以通过拓扑排序来解决，从而提高工作效率和准确性。

详解C++实现拓扑排序算法⽬录⼀、拓扑排序的介绍⼆、拓扑排序的实现步骤三、拓扑排序⽰例⼿动实现四、拓扑排序的代码实现五、完整的代码和输出展⽰⼀、拓扑排序的介绍拓扑排序对应施⼯的流程图具有特别重要的作⽤，它可以决定哪些⼦⼯程必须要先执⾏，哪些⼦⼯程要在某些⼯程执⾏后才可以执⾏。

为了形象地反映出整个⼯程中各个⼦⼯程(活动)之间的先后关系，可⽤⼀个有向图来表⽰，图中的顶点代表活动(⼦⼯程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进⾏。

通常，我们把这种顶点表⽰活动、边表⽰活动间先后关系的有向图称做顶点活动⽹(Activity On Vertex network)，简称AOV⽹。

⼀个AOV⽹应该是⼀个有向⽆环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都⽆法进⾏（对于数据流来说就是死循环）。

在AOV⽹中，若不存在回路，则所有活动可排列成⼀个线性序列，使得每个活动的所有前驱活动都排在该活动的前⾯，我们把此序列叫做拓扑序列(Topological order)，由AOV⽹构造拓扑序列的过程叫做拓扑排序(Topological sort)。

AOV⽹的拓扑序列不是唯⼀的，满⾜上述定义的任⼀线性序列都称作它的拓扑序列。

⼆、拓扑排序的实现步骤1.在有向图中选⼀个没有前驱的顶点并且输出2.从图中删除该顶点和所有以它为尾的弧（⽩话就是：删除所有和它有关的边）3.重复上述两步，直⾄所有顶点输出，或者当前图中不存在⽆前驱的顶点为⽌，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断⼀个图是否有环。

三、拓扑排序⽰例⼿动实现如果我们有如下的⼀个有向⽆环图，我们需要对这个图的顶点进⾏拓扑排序，过程如下：⾸先，我们发现V6和v1是没有前驱的，所以我们就随机选去⼀个输出，我们先输出V6，删除和V6有关的边，得到如下图结果：然后，我们继续寻找没有前驱的顶点，发现V1没有前驱，所以输出V1，删除和V1有关的边，得到下图的结果：然后，我们⼜发现V4和V3都是没有前驱的，那么我们就随机选取⼀个顶点输出（具体看你实现的算法和图存储结构），我们输出V4，得到如下图结果：然后，我们输出没有前驱的顶点V3，得到如下结果：然后，我们分别输出V5和V2，最后全部顶点输出完成，该图的⼀个拓扑序列为：v6–>v1—->v4—>v3—>v5—>v2四、拓扑排序的代码实现下⾯，我们将⽤两种⽅法来实现我么的拓扑排序：1.Kahn算法2.基于DFS的拓扑排序算法⾸先我们先介绍第⼀个算法的思路：Kahn的算法的思路其实就是我们之前那个⼿动展⽰的拓扑排序的实现，我们先使⽤⼀个栈保存⼊度为0 的顶点，然后输出栈顶元素并且将和栈顶元素有关的边删除，减少和栈顶元素有关的顶点的⼊度数量并且把⼊度减少到0的顶点也⼊栈。

拓扑排序求最长路径1. 什么是拓扑排序？拓扑排序是对有向无环图（DAG）进行排序的一种算法。

在有向图中，如果存在一条从节点A到节点B的有向边，那么节点A就必须在节点B之前进行排序。

拓扑排序通过将图中的节点按照一定的顺序进行排列，使得任意两个节点之间不存在环。

拓扑排序可以应用于许多问题，比如任务调度、依赖关系分析等。

2. 拓扑排序算法2.1. 算法原理拓扑排序算法基于深度优先搜索（DFS）或广度优先搜索（BFS）实现。

其基本思想是通过遍历图中的所有节点，并记录每个节点的入度（即指向该节点的边数）。

然后从入度为0的节点开始遍历，并将其加入结果列表中。

然后将与该节点相邻的节点的入度减1，并将新入度为0的节点加入结果列表。

重复此过程直到所有节点都被加入结果列表。

2.2. 算法步骤以下是拓扑排序算法的详细步骤：1.初始化一个空结果列表result和一个空队列queue。

2.遍历图中所有节点，并统计每个节点的入度。

3.将入度为0的节点加入队列queue。

4.当队列queue不为空时，执行以下步骤：–从队列queue中取出一个节点node，并将其加入结果列表result。

–遍历与节点node相邻的所有节点，并将它们的入度减1。

–如果某个节点的入度减为0，则将其加入队列queue。

5.如果结果列表result的长度等于图中的节点数，则说明拓扑排序成功；否则，说明图中存在环。

以下是使用Python语言实现拓扑排序算法的示例代码：from collections import defaultdict, dequedef topological_sort(graph):# 统计每个节点的入度in_degree = defaultdict(int)for node in graph:for neighbor in graph[node]:in_degree[neighbor] += 1# 初始化结果列表和队列result = []queue = deque()# 将入度为0的节点加入队列for node in graph:if in_degree[node] == 0:queue.append(node)# 拓扑排序while queue:node = queue.popleft()result.append(node)for neighbor in graph[node]:in_degree[neighbor] -= 1if in_degree[neighbor] == 0:queue.append(neighbor)if len(result) == len(graph):return resultelse:return None3. 拓扑排序求最长路径在有向无环图中，求最长路径可以通过拓扑排序算法来实现。

dfs实现拓扑排序原理
深度优先搜索 (DFS) 是一种用于遍历或搜索图或树的算法。

拓扑排序是一种特
定形式的图排序，其中图中的顶点按照一定的规则进行排序，使得任何一个顶点的边都指向排在其后面的顶点。

DFS 实现拓扑排序的原理如下：
1. 首先，选择一个起始顶点（或节点）开始遍历整个图。

将该顶点标记为已访问。

2. 对于当前访问的顶点，依次访问它的所有未被访问过的邻居顶点。

这可以通
过递归的方式实现。

3. 递归地访问当前顶点的邻居顶点，并将它们标记为已访问。

4. 当没有未被访问的邻居顶点时，将当前顶点添加到拓扑排序结果的头部（或
尾部）。

5. 回溯到上一个顶点，重复步骤3和步骤4，直到所有顶点都被访问过。

6. 最后得到的拓扑排序结果即为所需的结果。

通过上述步骤，DFS 实现了拓扑排序的原理。

它的核心思想是尽可能深入地访
问某个分支，直到无法继续深入为止，然后回溯到上一个节点，继续访问其他分支，直到遍历完整个图。

需要注意的是，拓扑排序只适用于有向无环图 (DAG)，即图中不存在环路。

否则，无法对图进行拓扑排序。

在实际应用中，拓扑排序广泛应用于任务调度、依赖关系分析等领域。

希望以上内容能够满足您对DFS实现拓扑排序原理的描述需求。

若需要更详
细的解释或其他问题，请随时提问。

拓扑排序和广度深度关系拓扑排序是一种对有向无环图(Directed Acyclic Graph, DAG)进行排序的算法，它能够找出图中节点的一种线性排序，使得对于任意一对有向边(u, v)，在排序中节点u都出现在节点v之前。

拓扑排序在诸多领域中有着广泛的应用，其中之一就是图论中的拓扑结构分析。

而广度优先搜索和深度优先搜索则是两种常用的图遍历算法，它们与拓扑排序有着密切的关系。

我们来了解一下拓扑排序的基本原理和步骤。

拓扑排序的过程可以用来解决一些实际问题，例如任务调度、依赖关系分析等。

在拓扑排序中，首先找到图中入度为0的节点，将其加入到排序结果中，并将其从图中删除。

然后更新剩余节点的入度，再次找到入度为0的节点，重复上述步骤，直到所有节点都被加入到排序结果中，或者图中不存在入度为0的节点为止。

如果所有节点都被加入到排序结果中，则说明图中不存在环，即是一个有向无环图。

如果图中仍然存在入度不为0的节点，则说明图中存在环，无法进行拓扑排序。

广度优先搜索和深度优先搜索是两种常用的图遍历算法。

广度优先搜索从图的起始节点开始，逐层遍历图中的节点，直到遍历完所有节点为止。

在遍历的过程中，使用一个队列来保存待访问的节点。

深度优先搜索则是从图的起始节点开始，沿着一条路径尽可能深地访问图中的节点，直到到达叶子节点或无法继续访问为止。

在遍历的过程中，使用一个栈来保存待访问的节点。

拓扑排序和广度优先搜索之间存在紧密的联系。

事实上，拓扑排序算法中的每一步都可以看作是广度优先搜索过程中的一次层次遍历。

在拓扑排序中，每次选择入度为0的节点加入到排序结果中，相当于广度优先搜索中将节点加入到队列中，并以此节点为起始节点，继续遍历其相邻节点。

因此，拓扑排序可以看作是广度优先搜索的一种应用。

拓扑排序和深度优先搜索之间也存在关系。

在深度优先搜索过程中，当访问到一个节点时，会继续递归地访问其相邻节点，直到到达叶子节点或无法继续访问为止。

有向无环图的拓扑排序实验总结
有向无环图（Directed Acyclic Graph, DAG）是有向图的一种，字面意思的理解就是图中没有环。

常常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。

拓扑排序是对DAG的顶点进行排序，使得对每一条有向边(u, v)，均有u（在排序记录中）比v 先出现。

亦可理解为对某点v而言，只有当v的所有源点均出现了，v才能出现。

拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序的操作。

拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。

拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。

DAG在区块链中得到很广泛的应用哦。

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V, E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

图按照边的有无方向性分为无向图和有向图。

图中某个节点与其他节点的直连边条数称为该节点的度。

有向图中，指向其他节点的边成为出度，被其他节点指向的边称为入度。

如果在有向图中，无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。

偏序，集合内只有部分元素之间在这个关系下是可以比较的，比如：比如复数集中并不是所有的数都可以比较大小，那么“大
小”就是复数集的一个偏序关系。

全序，集合内任何一对元素在在这个关系下都是相互可比较的，比如：有限长度的序列按字典序是全序的。

最常见的是单词在字典中是全序的。

成绩14信计 2015-2016（一）数据结构课程设计设计题目拓扑排序设计时间——学生姓名冯佳君学生学号20140401105所在班级14信计 1指导教师刘风华徐州工程学院数学与物理科学学院一、需求剖析1.问题描绘本次课程设计题目是：用毗邻表结构图而后进行拓扑排序，输出拓扑排序序列。

拓扑排序的基本思想为：1)从有向图中选一个无前驱的极点输出；2)将此极点和以它为起点的弧删除；3)重复 1) 、 2) 直到不存在无前驱的极点；4)若此时输出的极点数小于有向图中的极点数，则说明有向图中存在回路，不然输出的极点的次序即为一个拓扑序列。

2.拓扑排序有向图拓朴排序算法的基本步骤以下：1 ）从图中选择一个入度为0 的极点，输出该极点；2 ）从图中删除该极点及其有关系的弧，调整被删弧的弧头结点的入度（入度-1 ）；3）重复履行 1）、 2）直到全部极点均被输出，拓朴排序达成或许图中再也没有入度为 0 的极点（此种状况说明原有向图含有环）。

3．基本要求(1)输入的形式和输入值的范围；第一是输入要排序的极点数和弧数，都为整型，中间用分开符分开；再输入各极点的值，为正型，中间用分开符分开；而后输入各条弧的两个极点值，先输入弧头，再输入弧尾，中间用分开符分开，输入的值只好是开始输入的极点值不然系统会提示输入的值的极点值不正确，请从头输入，只需持续输入正确的值就行。

(2)输出的形式；第一输出成立的毗邻表，而后是最后各极点的出度数，再是拓扑排序的序列，而且每输出一个极点，就会输出一次各极点的入度数。

(3)程序所能达到的功能；因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列，在一个有向图中，若用极点表示活动，有向边就表示活动间先后次序，那么输出的拓扑序列就表示各极点间的关系为反应出各点的储存结构，以毗邻表储存并输出各极点的入度。

二、纲要设计1.算法顶用到的全部各样数据种类的定义在该程序顶用毗邻表作为图的储存结构。

【图论】有向⽆环图的拓扑排序1. 引⾔有向⽆环图（Directed Acyclic Graph, DAG）是有向图的⼀种，字⾯意思的理解就是图中没有环。

常常被⽤来表⽰事件之间的驱动依赖关系，管理任务之间的调度。

拓扑排序是对DAG的顶点进⾏排序，使得对每⼀条有向边(u, v)，均有u（在排序记录中）⽐v先出现。

亦可理解为对某点v⽽⾔，只有当v的所有源点均出现了，v才能出现。

下图给出有向⽆环图的拓扑排序：下图给出的顶点排序不是拓扑排序，因为顶点D的邻接点E⽐其先出现：2. 算法原理与实现拓扑排序的实现算法有两种：⼊度表、DFS，其时间复杂度均为O(V+E)。

⼊度表对于DAG的拓扑排序，显⽽易见的办法：找出图中0⼊度的顶点；依次在图中删除这些顶点，删除后再找出0⼊度的顶点；然后再删除……再找出……直⾄删除所有顶点，即完成拓扑排序为了保存0⼊度的顶点，我们采⽤数据结构栈（亦可⽤队列）；算法的可视化可参看。

图⽤邻接表（adjacency list）表⽰，⽤数组inDegreeArray[]记录结点的⼊度变化情况。

C实现：// get in-degree arrayint *getInDegree(Graph *g) {int *inDegreeArray = (int *) malloc(g->V * sizeof(int));memset(inDegreeArray, 0, g->V * sizeof(int));int i;AdjListNode *pCrawl;for(i = 0; i < g->V; i++) {pCrawl = g->array[i].head;while(pCrawl) {inDegreeArray[pCrawl->dest]++;pCrawl = pCrawl->next;}}return inDegreeArray;}// topological sort functionvoid topologicalSort(Graph *g) {int *inDegreeArray = getInDegree(g);Stack *zeroInDegree = initStack();int i;for(i = 0; i < g->V; i++) {if(inDegreeArray[i] == 0)push(i, zeroInDegree);}printf("topological sorted order\n");AdjListNode *pCrawl;while(!isEmpty(zeroInDegree)) {i = pop(zeroInDegree);printf("vertex %d\n", i);pCrawl = g->array[i].head;while(pCrawl) {inDegreeArray[pCrawl->dest]--;if(inDegreeArray[pCrawl->dest] == 0)push(pCrawl->dest, zeroInDegree);pCrawl = pCrawl->next;}}}时间复杂度：得到inDegreeArray[]数组的复杂度为O(V+E)；顶点进栈出栈，其复杂度为O(V)；删除顶点后将邻接点的⼊度减1，其复杂度为O(E)；整个算法的复杂度为O(V+E)。

有向无环图的拓扑排序
有向无环图的拓扑排序是一种特殊的排列，它涉及在一组元素的拓扑结构中，将各元素按照一定的次序排列起来。

它有两个基本的要求：一是有向无环图，即不能存在任何环路；二是任何一条边必须从一个先序节点指向后序节点，以此来确定对应的拓扑排序结果。

在进行拓扑排序时，首先需要先把图中的环路找出来，把有向无环图分成多个相互独立的阶段，并分别按照阶段求解各阶段的拓扑排序，然后将各阶段的拓扑排序按照图中指定节点先后顺序排列起来，就可以得到这张有向无环图的拓扑排序。

拓扑排序在许多领域都有着重要的应用，例如安排任务时，我们可以借助拓扑排序来找出关联之间的正确的顺序；编译器在编译程序时，也会借助拓扑排序来指定并实现不同类型的操作次序；MRP（Materials Requirements Planning，物料需求计划）系统可以采用拓扑排序帮助企业采购计划统一管理生材料及半成品库存清单等等。

从上述可知，有向无环图的拓扑排序是一个非常重要的数学算法，它可以帮助我们解决大量实际的问题，发挥着极其重要的作用。

拓扑排序算法题
题目：拓扑排序
给定一个有向图，请输出其拓扑排序结果。

拓扑排序是一种对有向无环图（DAG）进行排序的算法，它会生成一个线性序列，使得对于任何从顶点 u 到顶点 v 的有向边 uv，u 在排序中都出现在 v 之前。

输入格式：
第一行包含两个整数 n 和 m，分别表示有向图中的顶点数和边数。

接下来 m 行，每行包含两个整数 u 和 v，表示一条从顶点 u 到顶点 v 的有向边。

输出格式：
输出一行，包含 n 个整数，表示拓扑排序的结果。

如果有多组解，则输出任意一组即可。

数据范围：
1 <= n <= 1000
1 <= m <= 20000
样例输入：
5 5
1 2
2 3
3 4
4 5
5 1
样例输出：
1 2 3 4 5
解题思路：
拓扑排序算法的思路是不断从有向图中删除入度为 0 的顶点，并将其加入结果序列中，直到所有顶点都被删除或发现有环为止。

因此，我们可以使用队列来实现该算法。

具体步骤如下：
1. 创建一个空队列和一个空结果序列。

2. 遍历所有顶点，将入度为 0 的顶点加入队列中。

3. 从队列中取出一个顶点，将其加入结果序列中，并将其从有向图中删除。

同时，减小与其相连的所有顶点的入度，并将入度变为0 的顶点加入队列中。

4. 重复步骤 3 直到队列为空或发现有环为止。

5. 如果结果序列中的顶点个数等于有向图中的顶点个数，则输出结果序列；否则说明有环，无法进行拓扑排序。