图--拓扑排序

拓扑排序——判断有向图中是否存在环 1// 将先修关系构成⼀张图，由每个数对的第⼆个数字向第⼀个数字连边。

2// ⾸先将所有⼊度为0的点进队，准备拓扑排序。

3// 宽搜过程中，将当前结点所关联的结点的⼊度减1；若发现新的⼊度为0的结点，则将其进队。

4// 最后如果遍历了所有结点，则说明可以满⾜要求；否则，先修关系存在环。

56//查找是否有环7class Solution8 {9public:10bool canFinish(int numCourses, vector<vector<int>>& prerequisites)11 {12 vector<vector<int>> graph(numCourses);13 vector<int> in_degree(numCourses, 0);14for (int i = 0; i < prerequisites.size(); i++)15 {16 in_degree[prerequisites[i][0]]++;17 graph[prerequisites[i][1]].push_back(prerequisites[i][0]);18 }1920 queue<int> q;21 vector<bool> vis(numCourses, false);2223for (int i = 0; i < numCourses; i++)24if (in_degree[i] == 0)25 q.push(i);26while (!q.empty())27 {28int sta = q.front();29 q.pop();30 vis[sta] = true;31//有哪些邻边32for (int i = 0; i < graph[sta].size(); i++)33 {34 in_degree[graph[sta][i]]--;// ⼊度-135if (in_degree[graph[sta][i]] == 0) //⼊度如果为0，加⼊队列36 q.push(graph[sta][i]);37 }38 }3940//0->1->241for (int i = 0; i < numCourses; i++)42if (vis[i] == false)43return false;//有环44return true;//⽆环45 }46 };。

图基本算法拓扑排序（基于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）的排序算法，它可以将图中的顶点按照一定的顺序进行排序，使得图中任意一条有向边的起点在排序结果中都排在终点的前面。

在实际应用中，拓扑排序算法常用于解决任务调度、依赖关系分析等问题。

本文将详细介绍拓扑排序算法的原理、实现方法以及应用场景。

### 一、拓扑排序算法原理拓扑排序算法的原理比较简单，主要包括以下几个步骤：1. 从DAG图中选择一个入度为0的顶点并输出。

2. 从图中删除该顶点以及以该顶点为起点的所有有向边。

3. 重复步骤1和步骤2，直到图中所有顶点都被输出。

### 二、拓扑排序算法实现下面以Python语言为例，给出拓扑排序算法的实现代码：```pythondef topological_sort(graph):in_degree = {v: 0 for v in graph}for u in graph:for v in graph[u]:in_degree[v] += 1queue = [v for v in graph if in_degree[v] == 0] result = []while queue:u = queue.pop(0)result.append(u)for v in graph[u]:in_degree[v] -= 1if in_degree[v] == 0:queue.append(v)if len(result) == len(graph):return resultelse:return []# 测试代码graph = {'A': ['B', 'C'],'B': ['D'],'C': ['D'],'D': []}print(topological_sort(graph))```### 三、拓扑排序算法应用场景拓扑排序算法在实际应用中有着广泛的应用场景，其中包括但不限于以下几个方面：1. 任务调度：在一个任务依赖关系图中，拓扑排序可以确定任务的执行顺序，保证所有任务按照依赖关系正确执行。

在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。

如下图是计算机专业课程之间的先后关系：3. 2 拓扑排序在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。

如上图的拓扑排序:基础知识；Pascal；数据结构；离散数学。

或基础知识；离散数学Pascal；数据结构。

拓扑排序的方法和步骤：（1）在图中选一个没有前趋的顶点并输出之（2）删除该顶点及由它发出的各边，直到图中不存在没有前趋的顶点为止。

若输出的顶点数小于AOV网中的顶点数，则图中存在回路，拓扑排序无法进行，否则输出的顶点系列就是一种拓扑系列。

以下是将一AOV网进行拓扑排序的算法：网采用邻接矩阵A表示,若a[i，j]=1，表示活动i先于j，a[i，j]=0，表示活动i与j不存在先后关系。

（1）计算各顶点的入度；（2）找入度为零的点输出之，删除该点及以该点为起点的所有关联边，同时与该点关联各点的入度减1；（3）若所有顶点都输出完毕；若输出的顶点数小于AOV网中的顶点数，输出“存在回路”。

程序如下：program tppv;const maxn=100;varmap:array[1..maxn,1..maxn] of byte;into:array[1..maxn] of byte;n,i,j,k:byte;procedure init;vari,j:integer;beginread(n);for i:=1 to n dofor j:=1 to n doread(map[i,j]);inc(into[j]);end;end;begininit;for i:=1 to n dobeginj:=1;while (j<=n)and(into[j]<>0) do inc(j);write(j,' ');into[j]:=255;for k:=1 to n doif map[j,k]=1 then dec(into[k]);end;end.3.３应用举例与练习例：士兵排队问题：有N个士兵（1<=N<=100),编号依次为1,2,...,N.队列训练时，指挥官要把士兵从高到矮排成一行，但指挥官只知道“1 比2 高，7 比 5高”这样的比较结果。

拓扑排序求最长路径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. 拓扑排序求最长路径在有向无环图中，求最长路径可以通过拓扑排序算法来实现。

图-拓扑排序概念将有向图中的顶点以线性⽅式进⾏排序，是指对于任何连接⾃顶点u到顶点v的有向边uv，在最后的排序结果中，顶点u总是出现在顶点v的前⾯。

例如，图的顶点可能代表将要被执⾏的任务，边代表⼀个任务必须在另⼀个任务之前执⾏。

在该应⽤场景中，⼀个拓扑排序结果就是⼀个有效的任务序列。

前置条件⼀个有向图能进⾏拓扑排序的充要条件是，它是⼀个有向⽆环图，Directed Acyclic Graph。

任意DAG⾄少有⼀个拓扑排序结果，并且已知算法可以在线性时间内为任意DAG产⽣⼀个拓扑排序结果。

⽰例拓扑排序的⼀个典型应⽤是，基于任务之间的依赖关系，安排⼀个执⾏序列。

任务⽤顶点表⽰，从顶点x指向顶点y的边表⽰任务x必须在任务y开始之前完成。

⼀个拓扑排序结果可以给出执⾏这些任务的⼀个顺序。

在计算机科学中，这样的应⽤场景有：指令调度，确定makefile中的编译任务顺序，数据序列化，链接器中的符号依赖。

左图可能有以下有效的拓扑排序结果：5，7，3，11，8，2，9，10（从左到右，从上到下）3，5，7，8，11，2，9，10（⼩编号优先）5，7，3，8，11，10，9，2（最少边数优先）7，5，11，3，10，8，9，2（⼤编号优先）5，7，11，2，3，8，9，10（从上到下，从左到右）算法通常，拓扑排序算法的时间复杂度是顶点数和边数之和的线性关系。

O(|V|+|E|)。

1. Kahn算法⾸先，找到起始结点（start nodes）列表，并指导它们放⼊⼀个集合S中。

起始结点是指没有⼊边的结点，⼀个⾮空⽆环图中⾄少有⼀个这样的结点。

空链表L，将⽤于存放排好序的元素。

然后：while S is non-empty doremove a node n from Sadd n to tail of Lfor each node m with an edge e from n to m doremove edge e from the graphif m has no other incoming edges theninsert m into Sif graph has edges thenreturn error (graph has at least one cycle)elsereturn L(a topologically sorted order)每次从S中取出⼀个结点n，放⼊链表L中，然后遍历从该结点引出的所有边，从图中移除这条边，同时获取该边的另⼀个顶点，如果该顶点的⼊度在减去本边后为0，则也将它放⼊集合S中。

图的拓扑排序图的拓扑排序（TopologicalSorting）是指将一个有向无回路的图的顶点排序的方法。

它的表示和排序经常是一个有向图的核心。

有许多应用，用拓扑排序实现，比如活动安排问题、调度问题等，也能应用在计算机科学中，比如求解依赖关系等。

图的拓扑排序实际上是个结构优化问题，要求以最少的顶点构成图，使得它能够完整描述一个有向无回路图。

“拓扑排序”这个名称源自拓扑学，它是一种研究许多结构的学科，主要是用来描述无自循环的有向图的结构特性。

拓扑排序则是根据拓扑学来对给定的图进行排序，以使其有序化。

拓扑排序的基本原理是从一个有向图开始，把它分解成多个有向图的子图，而每个子图只有一个顶点没有出度。

从其中一个没有出度的顶点开始，把它加入到一个结果序列，接着从它的邻节点中选择一个没有出度的顶点，加入到结果序列中，直到所有顶点加入到结果序列中，就得到了一个有序的拓扑排序结果。

在有向图的拓扑排序中，有若干种算法，如拓扑排序算法、Kahn 算法、深度优先搜索算法等，它们经常用来在有向图中完成拓扑排序。

拓扑排序算法要求每个节点拥有一个入度（可以理解为前驱节点的个数），会用入度为0的节点来构成起点，然后按照节点的入度从小到大的顺序搜索，直到所有节点都被搜索。

Kahn算法与拓扑排序算法类似，它使用一个队列，从0入度的节点开始，把所有的0入度的节点入队，然后按照它们的出度，从队列里取出每一个节点，把节点的所有后继节点减1入度，如果减完之后发现有入度为0的节点，那么就入队，直到队列为空，就可以完成拓扑排序。

深度优先搜索算法也可以用来进行拓扑排序，它的基本思想是，从一个节点开始，按照深度优先搜索的方式，把节点进行拓扑排序，直到所有节点都被搜索完毕，就可以得到一个拓扑排序的序列。

在实际应用中，拓扑排序经常被用来解决活动安排问题和调度问题，因为这些问题都可以抽象成图模型来表示，而图的拓扑排序可以由此得到一个有序的序列，使得它们能够在正确的时序内完成。

详解图的应用（最小生成树、拓扑排序、关键路径、最短路径）1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树1.1 问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。

这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。

在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。

n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢?1.2 分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。

对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。

即无向连通图的生成树不是唯一的。

连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。

图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n 个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1 条边。

1.3最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。

最小生成树的性质：假设N=(V,{ E}) 是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。

1.4 解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。

他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。

时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V 为网图中所有顶点的集合，E 为网图中所有带权边的集合。

【图论】有向⽆环图的拓扑排序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)。

n,m有向无环图的拓扑排序
拓扑排序是一个有向无环图（DAG）排序的应用。

它可以帮助我们解决模型建模中的问题，例如工作流中的任务依赖，计算机网
络的路由，软件开发的构建顺序等等。

一个典型的拓扑排序图如下所示：图中由n个节点和m条有向边组成，如果图中存在一个有效的拓扑排序，那么它可以按照有向
边从属后面的节点开始确定一个排序。

拓扑排序是通过在有向无环图上采用贪心算法来实现的。

它从这个图中选取一个顶点，然后按照给定的顺序把它们添加到
最终的拓扑排序中，这个顶点的每个后继都会在它之前出现。

选
取的顶点必须满足两个条件：一是它没有任何前驱节点，即不存
在任何其它节点指向它；二是它的当前收缩度最高，即它的所有
出边（后继）数量最少。

特别的，当图中仍存在未被选取的顶点，而图中不存在满足上述条件的顶点时，可以认为图中不存在拓扑
排序。

因此，当我们想解决模型建模中的问题时，拓扑排序这个工具是非常有用的，它可以帮助我们快速排列和分析有向无环图中的节点，从而使模型建模更加顺利。

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

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

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

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

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

有向图算法之拓扑排序拓扑排序的意思： 对⼀个(Directed Acyclic Graph简称DAG)G进⾏拓扑排序，是将G中所有顶点排成⼀个线性序列，使得图中任意⼀对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。

通常，这样的线性序列称为满⾜拓扑次序(Topological Order)的序列，简称拓扑序列。

⼀个较⼤的⼯程往往被划分成许多⼦⼯程，我们把这些⼦⼯程称作活动(activity)。

在整个中，有些⼦⼯程(活动)必须在其它有关⼦⼯程完成之后才能开始，也就是说，⼀个⼦⼯程的开始是以它的所有前序⼦⼯程的结束为先决条件的，但有些⼦⼯程没有先决条件，可以安排在任何时间开始。

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

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

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

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

由AOV⽹构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每⼀项活动时，能够保证它的所有前驱活动都已完成，从⽽使整个⼯程顺序进⾏，不会出现冲突的情况。

拓扑排序的步骤：　 由AOV⽹构造拓扑序列的拓扑排序算法主要是循环执⾏以下两步，直到不存在⼊度为0的顶点为⽌。

(1) 选择⼀个⼊度为0的顶点并输出之； (2) 从⽹中删除此顶点及所有。