手撕数据结构与算法——拓扑排序

拓扑排序是图论中的一个重要概念，它在许多领域如任务调度、课程规划等都有广泛的应用。在这篇文章中，我们将探讨拓扑排序的基本概念、算法实现以及在C/C++中的实现方法。

拓扑排序简介

拓扑排序是针对有向无环图（DAG）的一种排序算法，它将图中的所有顶点排成一个线性序列，使得对于任何一条有向边U→V，顶点U都在顶点V的前面。这样的排序不是唯一的，因为可能存在多个有效的拓扑排序。

基本概念

有向无环图（DAG）：图中的边具有方向，且不存在环的图。环是指一个顶点序列，其中第一个顶点和最后一个顶点相同，并且序列中的每个顶点都直接或间接地指向下一个顶点。
入度（In-degree）：图中每个顶点指向它的边的数量。在拓扑排序中，入度为0的顶点表示没有其他顶点指向它的顶点。
拓扑序（Topological Order）：满足上述条件的顶点序列。

算法原理

拓扑排序通常使用两种方法实现：

基于Kahn算法的拓扑排序：
- 使用队列来存储所有入度为0的顶点。
- 从队列中取出一个顶点，将其加入到拓扑排序的结果列表中。
- 遍历该顶点的所有邻接点，将每个邻接点的入度减1。如果某个邻接点的入度变为0，则将其加入队列。
- 重复上述过程，直到队列为空。
基于DFS的拓扑排序：
- 使用递归来实现深度优先搜索（DFS）。
- 访问一个顶点时，先递归地访问其所有未访问的邻接点。
- 将当前顶点标记为已访问，并将其加入拓扑排序的结果列表中。
- 这种方法通常使用栈来存储拓扑排序的结果，以保证先访问的顶点最后加入栈中。

C/C++实现

下面我们将展示基于入度的算法在C++中的实现。

1. 定义图结构

首先，我们需要定义一个图结构，包括顶点、边以及顶点的入度。

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>using namespace std;class Graph {int V; // 顶点数vector<vector<int>> adj; // 邻接表vector<int> indegree; // 入度数组public:Graph(int V) : V(V), adj(V), indegree(V, 0) {}void addEdge(int v, int w) {adj[v].push_back(w);indegree[w]++;}void topologicalSort() {queue<int> q;for (int i = 0; i < V; i++) {if (indegree[i] == 0)q.push(i);}vector<int> topOrder;while (!q.empty()) {int u = q.front();q.pop();topOrder.push_back(u);for (int v : adj[u]) {indegree[v]--;if (indegree[v] == 0)q.push(v);}}if (topOrder.size() != V)cout << "Graph is not a DAG (Cycle detected)" << endl;elsefor (int i : topOrder)cout << i << " ";}
};

2. 使用图结构

创建一个图实例，并添加边，然后调用`topologicalSort`方法进行拓扑排序。

int main() {Graph g(6);g.addEdge(5, 2);g.addEdge(5, 0);g.addEdge(4, 0);g.addEdge(4, 1);g.addEdge(2, 3);g.addEdge(3, 1);cout << "Topological Sort: ";g.topologicalSort();return 0;
}

拓扑排序是处理有向无环图问题的有效工具，它在许多实际应用中都非常重要。通过上述C++代码，我们可以实现一个基本的拓扑排序算法，帮助我们理解和解决相关问题。

应用场景

任务调度：在任务之间存在依赖关系时，拓扑排序可以帮助确定任务的执行顺序。
课程规划：课程之间可能存在先修后修的关系，拓扑排序可以用来安排课程的上课顺序。
软件包管理：软件包之间可能存在依赖关系，拓扑排序可以用来确定安装顺序。