用c++拓扑排序非递归算法的实现

在 C++ 中实现拓扑排序的非递归算法通常会使用邻接表表示图的数据结构，并采用迭代的方式来避免函数调用栈过深的问题。以下是基于邻接列表的简单拓扑排序算法的步骤：

1. 初始化：创建一个队列用于存储入度为0的节点，将它们放入队列。同时，维护一个集合（如 `std::unordered_set` 或者 `std::vector<bool>`），标记已处理的节点。

2. 循环直到队列为空：
- 从队列中取出一个节点。
- 遍历该节点的所有邻居（通过邻接表），对于每个邻居，将其入度减一。如果邻居的入度变为0，那么加入队列并更新标记。

3. 检查是否所有节点都被处理了：如果队列为空并且所有节点都在集合中，说明完成了拓扑排序；否则，存在有向循环，图无法进行拓扑排序。

以下是简单的伪代码实现：

#include <queue>
using namespace std;

// 假设 AdjList 存储邻接列表
void topologicalSort(vector<int>& adjList, vector<int>& inDegree, vector<int>& result) {
    queue<int> q;
    unordered_set<int> visited;

    for (int i = 0; i < adjList.size(); ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
            visited.insert(i);
        }
    }

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        result.push_back(node); // 将当前节点添加到结果

        for (int neighbor : adjList[node]) {
            --inDegree[neighbor]; // 更新相邻节点的入度
            if (inDegree[neighbor] == 0 && !visited.count(neighbor)) {
                q.push(neighbor);
                visited.insert(neighbor);
            }
        }
    }

    if (visited.size() != adjList.size()) {
        cout << "Graph contains a cycle and cannot be sorted." << endl;
    } else {
        cout << "Topological sort: ";
        for (int node : result) {
            cout << node << " ";
        }
        cout << endl;
    }
}