kahn算法实现拓扑排序

1. 拓扑排序（Topological Sorting）是什么？

拓扑排序是一种用于 有向无环图（DAG, Directed Acyclic Graph）的节点排序算法。它的目标是将图中的所有节点排成一个 线性序列，使得对于图中每一条从节点 u 到节点 v 的有向边 u -> v，在排序中节点 u 都排在节点 v 的前面。

简单来说，如果图中有一条边 u -> v，那么在拓扑排序中，节点 u 必须排在节点 v 的前面。这个排序是图中所有节点的线性排列，并且保证了这种有向依赖关系。

2. 拓扑序列是什么？

拓扑序列是拓扑排序的结果，即节点的一个线性排列，满足上述的依赖关系。对于给定的有向无环图，可能存在多个不同的拓扑序列，只要它们满足图中所有边的依赖关系。

3. 拓扑排序的应用场景

拓扑排序通常用于需要考虑依赖关系的场景，比如：

任务调度：例如，某些任务需要在其他任务完成后才能开始工作，可以将任务的依赖关系表示为有向无环图，通过拓扑排序确定任务的执行顺序。
课程安排：如果某些课程有先修课要求，可以用拓扑排序来安排课程学习的顺序。
构建系统：如果某些模块需要依赖其他模块编译，可以通过拓扑排序决定编译顺序。

4. 如何进行拓扑排序？

有多种算法可以实现拓扑排序，最常用的有以下两种：

（1）Kahn算法（基于入度的算法）

思路：
- 找到所有 入度为0 的节点（即没有任何节点指向它们的节点）。
- 将这些节点从图中移除，并将它们的邻接节点的入度减1。
- 如果某个邻接节点的入度减为0，将它也加入排序序列中。
- 重复该过程，直到所有节点都被处理。
步骤：
1. 计算图中每个节点的入度（指向该节点的边的数量）。
2. 将所有 入度为0 的节点加入队列。
3. 从队列中取出一个节点，加入拓扑序列，并将该节点的邻接节点入度减1。
4. 如果某个邻接节点的入度变为0，将其加入队列。
5. 重复步骤3和4，直到队列为空。如果此时拓扑序列包含了所有节点，则排序成功；否则，说明图中存在环，无法进行拓扑排序。
Kahn算法的时间复杂度：O(V + E)，其中 V 是节点数，E 是边数。

（2）深度优先搜索（DFS）法

思路：
- 对图进行 DFS 遍历，在每次访问完成一个节点的所有邻接节点后，将该节点加入一个栈。
- 当所有节点都被访问完后，栈中的节点顺序即为拓扑排序的逆序。
步骤：
1. 对图中的每个未访问的节点执行 DFS。
2. 当遍历到某个节点时，先递归访问它的所有邻接节点（即访问所有依赖它的节点）。
3. 在访问完所有邻接节点后，将该节点加入栈。
4. 最后栈中节点的顺序就是拓扑序列。
DFS法的时间复杂度：O(V + E)，其中 V 是节点数，E 是边数。

5. 举例说明

图示：

1
2
3

5 → 0 ← 4
↓       ↑
2 → 3 → 1

有向图 表示：
- 任务 5 和 4 是任务 0 的前置任务，任务 5 也是任务 2 的前置任务。
- 任务 2 是任务 3 的前置任务，任务 3 是任务 1 的前置任务。
- 任务 4 是任务 0 的前置任务。
拓扑排序结果：
- 可能的 拓扑序列 为：4, 5, 2, 3, 1, 0。
- 也可能是：5, 4, 2, 3, 1, 0。

Kahn算法实现（队列实现）：

个人理解：将每个入度为0的顶点加入队列，然后依次处理，先加入拓扑序列，将其邻接结点入度减1后再判断是否为0，如果是就加入队列，然后将原节点推出队列，再获取队列第一个，直到队列为空

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 函数声明
vector<int> kahnTopologicalSort(int n, vector<vector<int>>& adjList);

int main() {
    int n = 6;  // 节点数量
    // 邻接表表示的图
    vector<vector<int>> adjList = {
        {},       // 节点 0
        {0},      // 节点 1 指向 0
        {3},      // 节点 2 指向 3
        {1},      // 节点 3 指向 1
        {0},      // 节点 4 指向 0
        {0, 2}    // 节点 5 指向 0 和 2
    };

    vector<int> topoOrder = kahnTopologicalSort(n, adjList);

    // 检查拓扑排序结果
    if (topoOrder.size() == n) {
        cout << "拓扑排序结果: ";
        for (int node : topoOrder) {
            cout << node << " ";
        }
        cout << endl;
    } else {
        cout << "图中存在环，无法进行拓扑排序。" << endl;
    }

    return 0;
}

// Kahn算法实现
vector<int> kahnTopologicalSort(int n, vector<vector<int>>& adjList) {
    vector<int> inDegree(n, 0);  // 记录每个节点的入度
    vector<int> topoOrder;       // 存储拓扑排序的结果

    // 计算每个节点的入度
    for (int i = 0; i < n; i++) {
        for (int neighbor : adjList[i]) {
            inDegree[neighbor]++;
        }
    }

    queue<int> q;  // 用于存放入度为0的节点

    // 将所有入度为0的节点加入队列
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // 处理队列中的节点
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        topoOrder.push_back(node);  // 将节点加入拓扑排序结果

        // 遍历该节点的所有邻接节点
        for (int neighbor : adjList[node]) {
            inDegree[neighbor]--;  // 将邻接节点的入度减1
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);  // 如果邻接节点的入度为0，加入队列
            }
        }
    }

    return topoOrder;  // 返回拓扑排序结果
}

6. 如何判断是否存在拓扑排序？

拓扑排序仅适用于 有向无环图（DAG），也就是说图中不能有环。如果图中存在环，则无法进行拓扑排序，因为环中的节点之间存在相互依赖，无法线性排序。因此，在进行拓扑排序的过程中，如果图中存在环，算法将无法处理完所有节点。对于 Kahn 算法而言，如果最终没有处理完所有节点（即队列中还有节点入度不为 0），则说明图中存在环。