[AIGC] 深入理解拓扑排序

文章目录

一. 什么是拓扑排序？

拓扑排序(Topological Sorting)是针对有向无环图（Directed Acyclic Graph，简称DAG）的一种排序算法。不同于我们常见的排序算法，它的作用是对DAG中的节点进行排序，以使得每一个有向边 ( u , v ) (u,v) (u,v) 从 u u u 到 v v v，均有 u u u 在 v v v 之前。换句话说，若存在一条从节点 u u u 到节点 v v v 的路径，那么排序后 u u u 必定在 v v v 之前。

二. 拓扑排序的应用

拓扑排序在工程实践中有着有着广泛的应用，如任务调度、课程表的安排等问题。例如在课程规划中，我们需要先修的课程必须在后修的课程之前被安排，这就是一个典型的拓扑排序问题。

三. 拓扑排序的算法过程

具体的拓扑排序的步骤如下：

 1. 首先在图中找到一个没有前驱，即入度为0的顶点，将其输出。 2. 将此顶点及其所有出边从图中删除。 3. 重复上述两步，直至全部顶点均已输出；或者新的图中不存在无前驱的顶点为止。 

在步骤3中，如果新的图中不存在无前驱的顶点，而图中又非空，则图中存在环，即原图不是有向无环图，不能进行拓扑排序。

拓扑排序的实现一般使用深度优先搜索或者广度优先搜索。具体的算法实现和详解可以参考一些常见的算法教科书和教程。

当然，我很乐意为你提供一些和拓扑排序相关的 LeetCode 题目以及代码实现。以下是我为你挑选的几个题目：

四、leetcode

1. 课程表 II（LeetCode 题号：210）

这道题目是上一题的进阶版，题目的要求基本相同，但现在你还需要输出一个拓扑排序。

Python代码实现：

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]: from collections import deque # 入度表 indegrees = [0 for _ in range(numCourses)] # 邻接表 adjacency = [[] for _ in range(numCourses)] # 队列 queue = deque() # 通过 prerequisites 得到入度表和邻接表 for cur, pre in prerequisites: indegrees[cur] += 1 adjacency[pre].append(cur) # 将所有入度为 0 的节点入队 for i in range(len(indegrees)): if not indegrees[i]: queue.append(i) # 拓扑排序 topo_order = [] while queue: pre = queue.popleft() topo_order.append(pre) numCourses -= 1 for cur in adjacency[pre]: # 将后继课程的入度 -1 indegrees[cur] -= 1 # 如果后继课程入度为 0，那么将其加入到队列中 if not indegrees[cur]: queue.append(cur) # 如果所有的课程都已经学完，那么返回拓扑排序，否则返回空列表 return topo_order if not numCourses else [] 

2. 课程表 III（LeetCode 题号：1136）

不好意思，上一条回复被意外地切断了。我们继续讲述上一题的内容。

3. 课程表 III（LeetCode 题号：630）

这个题目和课程表 I, II有些不同，课程表 III现在每门课程有了一定的持续时间，并且你必须在规定的最后一天完成。这道题的目标是你要找出可以完成的最大课程数。

Python代码实现：

def scheduleCourse(courses: list[list[int]]) -> int: import heapq # 首先按照结束时间对课程进行排序 courses.sort(key=lambda x: x[1]) q = [] # 当前的时间 now = 0 for time, end in courses: now += time heapq.heappush(q, -time) # 如果当前的时间大于课程的结束时间，那么就从已选的课程中剔除持续时间最长的课程 if now > end: now += heapq.heappop(q) return len(q) 

以上便是几道利用拓扑排序解决的题目，它们代表了拓扑排序在解决图的问题中的强大能力。希望对你有所帮助。如果需要更多的帮助或者有其他的问题，欢迎随时告诉我。

五. 注意事项

需要注意的是，拓扑排序也许不止一种。一个图的拓扑排序可能有多个，只要满足上述的条件，即可称为该图的一种拓扑排序。

以上就是关于拓扑排序的全部内容，希望能帮助大家深入理解和掌握这个重要的算法。