拓扑排序 —— 1.基本概念与核心算法

拓扑排序 —— 1.基本概念与核心算法

引用

CSDN

1.

https://blog.csdn.net/smileyan9/article/details/143221791

拓扑排序是一种用于有向无环图（DAG）的线性排序算法，广泛应用于任务调度、编译依赖关系、课程安排等多个领域。本文将从基本概念出发，详细介绍拓扑排序的核心算法及其应用场景，帮助读者系统地掌握这一重要算法。

1. 基本概念

1.1 知识预备

在学习拓扑排序之前，应当了解的基本概念包括：

• 图的基本概念：图、边、节点、邻接表等；
• 有向图与无向图：什么是有向图、什么是无向图等；
• 入度与出度：每个节点的入度、出度的概念与计算规则；
• 环：环是指在图中从一个节点出发，通过边回到原节点的路径。
• 深度优先搜索与广度优先搜索：什么是深度优先搜索，什么是广度优先搜索。

1.2 什么是拓扑排序

1.2.1 “拓扑” 是什么意思

“拓扑” 一词的由来

拓扑学的定义：拓扑学的起源可以追溯到19世纪，当时数学家们开始研究几何体在各种变形下如何保持不变的性质。这些性质被称为“拓扑性质”，例如连通性、紧致性等。

拓扑学中的“拓扑”：在拓扑学中，空间的结构通过一组规则（称为拓扑）来定义。这些规则描述了空间中点的邻近关系和如何通过连续变换保持空间的基本特性。

计算机科学中的“拓扑排序”：在计算机科学中，“拓扑”一词被借用来描述对有向图进行的排序，因为这种排序方式类似于拓扑学中的“拓扑”概念，即在有向图中按照一定的规则进行线性排列，以保留顶点间的依赖关系。

1.2.1 什么是拓扑排序

拓扑排序（Topological Sort）是对有向无环图（DAG）中的所有节点进行线性排序的一种算法，使得对于图中的每一条有向边u → v u \to vu→v，节点u uu在节点v vv之前出现在排序结果中。换句话说，拓扑排序提供了一种对图中所有节点的线性排列，使得所有的有向边都指向排序中的后续节点。

1.3 拓扑排序的简单例子

接下来以力扣第207题为例，介绍拓扑排序：
如下图所示：


左图中不存在环，因此可以完成拓扑排序；右图中存在环，可以理解为依赖关系存在矛盾，因此无法完成拓扑排序。
这里简单提一下解法：首先统计每个节点的入度，然后将所有入度为0的节点加入队列。接着，从队列中取出节点，减少其相邻节点的入度，如果相邻节点的入度变为0，则将其加入队列。如果所有节点都能按顺序加入队列，则图中无环，可以完成所有课程的学习。

1.4 拓扑排序的应用

拓扑排序是一种广泛应用于有向无环图（DAG, Directed Acyclic Graph）的算法，主要用于解决依赖关系问题，并且其算法高效且广泛应用于各种计算任务中。以下是几种典型的拓扑排序应用场景：

1.4.1 任务调度

• 场景：假设你有一组任务，其中一些任务必须在其他任务之前完成。这个问题可以用一个有向无环图来表示，其中每个任务是一个顶点，如果任务 A 必须在任务 B 之前完成，则有一条从 A 到 B 的边。拓扑排序可以帮助确定任务的执行顺序。
• 应用：项目管理中的任务排序、编译器中的编译顺序等。

1.4.2 编译依赖关系

• 场景：在大型软件工程项目中，模块之间往往有复杂的依赖关系。例如，一个模块可能依赖于其他模块的输出。通过构建一个依赖关系图，并对其进行拓扑排序，可以确保在编译时各个模块按照正确的顺序执行。
• 应用：构建系统（如 Makefile）中解决模块编译顺序。

1.4.3 课程安排

• 场景：在学术领域，课程通常有先修课程要求。例如，学生必须在修读某些高级课程之前完成特定的基础课程。通过将课程及其先修要求构建为有向无环图，可以使用拓扑排序来确定可行的课程修读顺序。
• 应用：大学课程规划系统。

1.4.4 数据序列化

• 场景：在数据库或其他数据存储中，表与表之间可能存在依赖关系。通过拓扑排序，可以决定表的插入或删除顺序，以避免违反外键约束。
• 应用：数据库中的数据导入导出顺序。

1.4.5 构建系统的依赖解析

• 场景：在构建系统中，模块之间可能有依赖关系。使用拓扑排序可以确定各个模块的构建顺序，确保所有依赖的模块都已被正确构建。
• 应用：软件构建系统（如 Maven、Gradle）的依赖管理。

1.4.6 电路设计中的先后关系

• 场景：在电路设计中，不同的组件之间存在依赖关系（如一个门的输出作为另一个门的输入）。通过拓扑排序可以确定组件的布局和连接顺序。
• 应用：电路板设计中的信号布线。

1.4.7 版本控制中的依赖关系

• 场景：在版本控制系统中，不同版本之间可能存在依赖关系。通过拓扑排序，可以确定哪些版本必须先被应用。
• 应用：软件版本控制中的依赖解决。

1.4.8 链路分析

• 场景：在网络或链路中，有时需要分析信息传播的路径和顺序。拓扑排序可以帮助确定信息在网络中的传递顺序。
• 应用：网络路由、社交网络中的信息传播路径分析。

拓扑排序是一种重要的工具，它帮助解决了各种需要处理依赖关系的复杂问题。在这些场景中，拓扑排序不仅提供了一个可行的执行顺序，还能帮助发现潜在的循环依赖问题。

1.5 拓扑排序的特点

拓扑排序具有以下几个关键特点：

1.5.1适用于有向无环图（DAG）

• 拓扑排序只能应用于有向无环图（DAG）。DAG 是一种图结构，其中没有任何顶点回到自身的路径，即不存在环。如果图中存在环，则无法进行拓扑排序。

1.5.2线性排序

• 拓扑排序的结果是图中所有顶点的一个线性排序。该排序使得对于图中的每一条有向边 (u, v)，顶点 u 都排在顶点 v 之前。这种排序确保了依赖关系的正确性。

1.5.3可能不唯一

• 一个给定的 DAG 可能有多个不同的拓扑排序结果。只要排序结果满足上述的依赖关系条件（即 u 在 v 之前），那么这个排序就是有效的。例如，对于某些顶点，如果它们之间没有直接依赖关系，它们的相对顺序可以有所不同。

1.5.4检测循环

• 拓扑排序可以用于检测图中的循环。如果在尝试进行拓扑排序时发现无法继续排序，这意味着图中存在环。在这种情况下，拓扑排序无法完成，表明依赖关系图中存在问题。

1.5.5时间复杂度

• 使用广度优先搜索（Kahn 算法）或深度优先搜索（DFS）的拓扑排序算法，其时间复杂度为 O(V + E)，其中 V 是图中的顶点数，E 是图中的边数。这使得拓扑排序在处理大规模图时仍然非常高效。

1.5.6局部顺序关系

• 拓扑排序确定的是一种全局的顺序关系，但这种顺序是基于局部的依赖关系。例如，如果任务 A 依赖于任务 B 和任务 C，则拓扑排序会确保 A 在 B 和 C 之后，但 B 和 C 之间的顺序可能并不固定，除非它们之间也有依赖关系。

1.5.7前置顶点

• 在拓扑排序中，每个顶点的前置顶点（即所有有向边指向该顶点的其他顶点）都排在它的前面。这保证了所有依赖项在当前顶点之前已经被处理。

2. 核心算法

拓扑排序的核心算法是用于有向无环图（DAG）的线性排序，使得对于图中的每一条有向边( u , v ) (u, v)(u,v)，顶点u uu都排在顶点v vv的前面。
拓扑排序的核心在于以下两个算法：

2.1Kahn’s Algorithm（基于入度）

Kahn’s Algorithm 是一种基于节点入度的拓扑排序算法。步骤如下：

• 步骤 1: 计算图中每个节点的入度（即指向该节点的边数）。
• 步骤 2: 将所有入度为 0 的节点入队列。
• 步骤 3: 当队列不为空时，执行以下操作：
• 从队列中取出一个节点，将其加入拓扑排序的结果列表。
• 遍历该节点的所有邻接节点，将这些邻接节点的入度减 1。
• 如果某个邻接节点的入度减为 0，则将其加入队列。
• 步骤 4: 如果拓扑排序包含的节点数等于图中的节点数，排序成功；否则图中存在环，无法进行拓扑排序。

代码示例（C++）：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> topologicalSortKahn(int V, vector<vector<int>>& adj) {
    vector<int> inDegree(V, 0);
    for (int i = 0; i < V; i++) {
        for (int v : adj[i]) {
            inDegree[v]++;
        }
    }
    queue<int> q;
    for (int i = 0; i < V; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    vector<int> topoOrder;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);
        for (int v : adj[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
    if (topoOrder.size() != V) {
        throw runtime_error("Graph has a cycle, no topological order exists.");
    }
    return topoOrder;
}
int main() {
    int V = 6;
    vector<vector<int>> adj(V);
    adj[5] = {0, 2};
    adj[4] = {0, 1};
    adj[2] = {3};
    adj[3] = {1};
    vector<int> topoOrder = topologicalSortKahn(V, adj);
    for (int v : topoOrder) {
        cout << v << " ";
    }
    return 0;
}

2.2Depth-First Search (DFS) Algorithm

另一种常用的拓扑排序方法是基于深度优先搜索（DFS）：

• 步骤 1: 对每个未访问的节点进行 DFS。
• 步骤 2: 在每次访问节点时，递归访问所有相邻节点。
• 步骤 3: 当一个节点的所有邻接节点都被访问过后，将该节点加入结果栈。
• 步骤 4: 完成所有节点的 DFS 后，结果栈中的节点顺序即为拓扑排序的顺序。

代码示例（C++）：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void dfs(int v, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& Stack) {
    visited[v] = true;
    for (int i : adj[v]) {
        if (!visited[i]) {
            dfs(i, adj, visited, Stack);
        }
    }
    Stack.push(v);
}
vector<int> topologicalSortDFS(int V, vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    stack<int> Stack;
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs(i, adj, visited, Stack);
        }
    }
    vector<int> topoOrder;
    while (!Stack.empty()) {
        topoOrder.push_back(Stack.top());
        Stack.pop();
    }
    return topoOrder;
}
int main() {
    int V = 6;
    vector<vector<int>> adj(V);
    adj[5] = {0, 2};
    adj[4] = {0, 1};
    adj[2] = {3};
    adj[3] = {1};
    vector<int> topoOrder = topologicalSortDFS(V, adj);
    for (int v : topoOrder) {
        cout << v << " ";
    }
    return 0;
}

总结

• Kahn’s Algorithm适合于入度信息明确的场景，通过入度为 0 的节点开始构建排序结果。
• DFS-Based Algorithm更适合在递归中处理复杂图的结构，通过递归逆序构建拓扑排序。