用C++编写实现拓扑排序非递归算法

在C++中，我们可以使用邻接表（Adjacency List）的数据结构来实现拓扑排序的非递归算法。拓扑排序主要用于有向无环图（DAG，Directed Acyclic Graph）中，对节点进行线性排列，使得所有的边都是从前面的节点指向后面的节点。

下面是一个简单的非递归算法步骤：

1. 使用哈希表存储每个节点的入度（in-degree），记录有多少条边进入该节点。
2. 遍历图，将所有入度为0的节点加入到结果列表中，并将其出度减1（即减少依赖项）。
3. 对于剩下的节点，如果它们的入度仍然为0，继续加入结果列表。
4. 重复第二步和第三步，直到所有节点都被处理过。

以下是伪代码和部分C++代码实现：

#include <vector>
using namespace std;

class Graph {
private:
    vector<int> indegrees; // 存储每个节点的入度
    vector<vector<int>> adjList; // 邻接表

public:
    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        indegrees[dest]++;
    }

    vector<int> topologicalSort() {
        vector<int> result;
        queue<int> q;

        // 初始化：入度为0的节点入队
        for (int i = 0; i < indegrees.size(); ++i) {
            if (indegrees[i] == 0)
                q.push(i);
        }

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

            result.push_back(node); // 将节点添加到结果列表
            for (int neighbor : adjList[node]) {
                indegrees[neighbor]--;
                if (indegrees[neighbor] == 0)
                    q.push(neighbor);
            }
        }

        return result.size() == indegrees.size() ? result : vector<int>(); // 如果所有节点都已处理，返回结果；否则表示有循环
    }
};

// 使用示例
Graph g;
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);

vector<int> sortedOrder = g.topologicalSort();