拓扑排序的实现过程

拓扑排序是一种有向无环图（DAG）的排序算法，将有向图中节点按照拓扑序列排列，具有广泛的应用场景，比如编译依赖关系、任务调度等领域。下面从算法原理、实现过程以及应用例子三个角度进行分析。

算法原理

拓扑排序的本质是对图的节点进行遍历，使得输出的序列中任何一对连续的节点都有从第一个节点到第二个节点的有向路径。算法流程如下：

1. 将 DAG 中所有入度为 0 的节点加入队列。

2. 取出队首节点，将其输出并删除所有以它为起点的有向边。

3. 重复步骤 2 直到队列为空。若此时仍有节点未输出，则说明图中存在环。

实现过程

在实现拓扑排序时，需要记录每个节点的入度以及各个节点之间的有向边。可以用邻接表或邻接矩阵表示图，这里以邻接表为例进行讲解。

Step 1：初始化

先将 DAG 中每个节点的入度都初始化为 0，再根据边列表构建邻接表。

```

vector > adj(n); //邻接表，adj[i] 存储 i 的所有后继节点

vector inDegree(n, 0); //入度数组

for (const auto& e : edges) { //edges 存储所有有向边

adj[e[0]].push_back(e[1]); //e[0] 是起点，e[1] 是终点

inDegree[e[1]]++; //e[1] 的入度加 1

}

```

Step 2：拓扑排序主函数

维护一个入度为 0 的节点队列，每次从队列中取出一个节点，将其后继节点的入度减 1，若后继节点入度为 0，则加入队列。

```

queue q;

for (int i = 0; i < n; i++) {

if (inDegree[i] == 0) { //将所有入度为 0 的节点加入队列

q.push(i);

}

}

vector res; //存储排序结果

while (!q.empty()) {

int cur = q.front();

q.pop();

res.push_back(cur); //加入结果

for (const auto& next : adj[cur]) { //遍历当前节点的所有后继节点

inDegree[next]--; //将后继节点的入度减 1

if (inDegree[next] == 0) { //若后继节点的入度为 0，则加入队列

q.push(next);

}

}

}

if (res.size() != n) { //图中存在环

return {};

}

return res;

```

应用例子

以课程安排为例，给出以下课程和依赖关系：

```

4, [[1,0],[2,0],[3,1],[3,2]]

```

其中第 i 门课程需要先修完以 edges[i][1] 为起点的课程。通过拓扑排序可以得到一种合理的上课顺序，即 0 -> 2 -> 1 -> 3 -> 4。实现代码如下：

```

vector findOrder(int numCourses, vector >& prerequisites) {

vector > adj(numCourses);

vector inDegree(numCourses, 0);

for (const auto& e : prerequisites) {

adj[e[1]].push_back(e[0]);

inDegree[e[0]]++;

}

queue q;

for (int i = 0; i < numCourses; i++) {

if (inDegree[i] == 0) {

q.push(i);

}

}

vector res;

while (!q.empty()) {

int cur = q.front();

q.pop();

res.push_back(cur);

for (const auto& next : adj[cur]) {

inDegree[next]--;

if (inDegree[next] == 0) {

q.push(next);

}

}

}

if (res.size() != numCourses) {

return {};

}

return res;

}

```