图--拓扑排序

拓扑排序——判断有向图中是否存在环 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的节点，那么就入队，直到队列为空，就可以完成拓扑排序。

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

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