[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)

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

五. 注意事项

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

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