Topological Sorting in Directed Acyclic Graphs (DAGs) for Job Scheduling with Dependencies

题目描述

假设我们有 n 个任务（标记为 0 到 n-1）需要完成。这些任务之间存在依赖关系：对于某些任务对 (u, v)，任务 u 必须在任务 v 之前完成。给定一个包含 m 个依赖关系的列表，每个依赖关系用一个二元组 [u, v] 表示，意味着任务 u 是任务 v 的前置任务。我们的目标是找到一个合法的任务执行顺序，使得所有依赖关系都得到满足。这种问题被称为拓扑排序，并且它只在任务依赖图是一个有向无环图 (Directed Acyclic Graph, DAG) 时才有解。

例如：
任务数 n = 4
依赖关系：[[1, 0], [2, 0], [3, 1], [3, 2]]
这意味着：

• 任务1必须在任务0之前完成。
• 任务2必须在任务0之前完成。
• 任务3必须在任务1之前完成。
• 任务3必须在任务2之前完成。

一个合法的拓扑排序结果是：[1, 2, 3, 0]。另一个结果是：[2, 1, 3, 0]。这里，任务1和2没有相互依赖，所以它们之间的顺序可以互换，但都必须出现在3和0之前。

解题过程

拓扑排序是一个经典的图论算法。我们将其分解为几个清晰的步骤。

第一步：问题建模与图表示

我们将每个任务看作图中的一个节点 (Vertex)。每个依赖关系 [u, v] 看作一条从节点 u 指向节点 v 的有向边 (Directed Edge)。这样，我们就构建了一个有向图。任务之间的依赖关系不能形成循环（即不能有环），否则就会出现“死锁”：比如任务A依赖B，B又依赖A，这就无法确定谁先执行。因此，有解的前提是图是一个DAG。

我们的目标：输出一个节点的线性序列，使得对于图中任意一条有向边 (u -> v)，节点 u 都出现在节点 v 之前。这样的序列称为拓扑序。

第二步：算法核心思想——入度与队列

拓扑排序有两种主流算法：Kahn算法（基于入度） 和 基于DFS的算法。这里我们讲解更直观、更常用的Kahn算法。

关键概念：入度 (In-degree)

• 一个节点的“入度”是指有多少条边指向它。
• 在依赖关系中，一个节点的入度代表了有多少个前置任务需要先完成。
• 如果一个节点的入度为0，意味着它没有任何前置任务，可以立即执行。

算法流程（Kahn算法）：

1. 初始化：
   • 计算图中每个节点的入度。
   • 将所有入度为0的节点加入一个队列（或列表）。
2. 循环处理：
   • 从队列中取出一个节点（记为 node）。
   • 将这个 node 加入到最终的结果序列（拓扑序）中。
   • 对于 node 的每一个邻居节点 neighbor（即 node 指向的节点）：
     • 将 neighbor 的入度减1（相当于“完成”了 node 这个前置任务）。
     • 如果 neighbor 的入度因此变为0，则将它加入队列。
3. 结束判断：
   • 重复步骤2，直到队列为空。
   • 最后，检查结果序列的长度。
     • 如果长度等于节点总数 n，说明我们成功为所有节点排序，找到了拓扑序。
     • 如果长度小于 n，说明图中存在环（有些节点的入度永远无法减到0），无法进行拓扑排序。

为什么这个算法有效？
算法从“源头”（入度为0的节点）开始，逐一“完成”它们，并移除它们对后续任务的影响（减少后续节点的入度）。每当一个节点所有的前置任务都被“完成”时（入度减至0），它就变成了新的“源头”，可以被处理。这个过程保证了在任何有向边 (u -> v) 中，u 总是在 v 之前被加入到结果序列。

第三步：逐步示例

让我们用开头的例子来手动模拟。

数据： n=4, edges = [[1,0], [2,0], [3,1], [3,2]]

1. 建图并计算入度：
   • 我们用邻接表表示图：graph[node] 是一个列表，存储 node 指向的所有节点。
     • graph[1] = [0]
     • graph[2] = [0]
     • graph[3] = [1, 2]
     • graph[0] = [] （任务0没有出边）
   • 计算每个节点的初始入度：
     • indegree[0] = 2 （有来自1和2的边）
     • indegree[1] = 1 （来自3）
     • indegree[2] = 1 （来自3）
     • indegree[3] = 0 （没有入边）
2. 初始化队列：
   • 将入度为0的节点加入队列。初始时，只有节点3的入度为0。
   • queue = [3]
   • result = []
3. 第一轮处理：
   • 从队列取出节点 3，加入结果：result = [3]。
   • 处理节点3的邻居：[1, 2]。
     • 对于邻居1：将其入度从1减为0。入度为0，加入队列。queue = [1]。
     • 对于邻居2：将其入度从1减为0。入度为0，加入队列。queue = [1, 2]。
4. 第二轮处理：
   • 取出节点 1，加入结果：result = [3, 1]。
   • 处理节点1的邻居：[0]。
     • 对于邻居0：将其入度从2减为1。入度不为0，不加入队列。queue = [2]。
5. 第三轮处理：
   • 取出节点 2，加入结果：result = [3, 1, 2]。
   • 处理节点2的邻居：[0]。
     • 对于邻居0：将其入度从1减为0。入度为0，加入队列。queue = [0]。
6. 第四轮处理：
   • 取出节点 0，加入结果：result = [3, 1, 2, 0]。
   • 节点0没有邻居，无需处理。
7. 结束：
   • 队列为空，停止循环。
   • 结果序列长度为4，等于总任务数。我们找到了一个拓扑序 [3, 1, 2, 0]。

注意，这个结果和之前提到的 [1, 2, 3, 0] 都是有效的，因为算法起始的入度为0的节点是3，所以先从3开始。不同的起始顺序会导致不同的合法拓扑序。

第四步：算法实现细节与代码框架（伪代码）

def topological_sort(num_tasks, prerequisites):
    """
    :param num_tasks: int, 任务数量n
    :param prerequisites: List[List[int]], 依赖关系列表，每个元素是 [u, v]
    :return: List[int], 拓扑序，如果存在环则返回空列表。
    """
    # 1. 初始化图结构和入度数组
    graph = [[] for _ in range(num_tasks)]
    indegree = [0] * num_tasks
    result = []

    # 2. 构建图和入度表
    for u, v in prerequisites:
        graph[u].append(v)  # u -> v
        indegree[v] += 1

    # 3. 初始化队列，将所有入度为0的节点入队
    from collections import deque
    queue = deque([i for i in range(num_tasks) if indegree[i] == 0])

    # 4. Kahn算法主循环
    while queue:
        node = queue.popleft()
        result.append(node)
        # 处理当前节点的所有后继节点
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # 5. 检查是否存在环
    if len(result) == num_tasks:
        return result
    else:
        return []  # 存在环，无法拓扑排序

第五步：复杂度分析与扩展

• 时间复杂度：O(V + E)。其中 V 是节点数（任务数 n），E 是边数（依赖关系数 m）。我们需要遍历所有节点来初始化，遍历所有边来建图和减入度，每个节点和边恰好被处理一次。
• 空间复杂度：O(V + E)。用于存储图的邻接表和入度数组。

扩展思考：

1. DFS方法：也可以使用深度优先搜索（DFS）配合节点的“状态”（未访问、访问中、已访问）来检测环并生成逆后序排列，其结果反转后即为拓扑序。
2. 多解输出：Kahn算法中，如果初始队列有多个节点，选择不同的节点顺序会产生不同的拓扑序。如果要求输出所有可能的拓扑序，需要使用回溯算法。
3. 应用场景：除了任务调度，拓扑排序还广泛应用于课程安排（先修课）、编译顺序（模块依赖）、项目管理、电子线路设计等任何存在依赖关系且需要线性化处理的领域。

关键总结：拓扑排序的核心在于识别并处理没有前置依赖（入度为0）的节点，逐步解除它们对后续节点的约束。Kahn算法通过维护入度表和队列，清晰、高效地实现了这一过程，并能自然地检测出图中是否存在环。