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

在C++中，拓扑排序是非递归的，通常用于有向无环图(DAG)中的任务调度、依赖关系解决等场景。以下是一个简单的拓扑排序算法实现：

#include <vector>
#include <list>

// 定义边的关系
using namespace std;

class Edge {
public:
    int src, dest;
    Edge(int s, int d) : src(s), dest(d) {}
};

// 有向图节点，记录入度
class GraphNode {
private:
    vector<int> inDegree; // 存储指向该节点的边的数量

public:
    void addEdge(Edge edge) {
        inDegree[edge.dest]++;
    }

    bool hasOutDegree() { return !inDegree.empty(); }
};

bool isTopologicalOrder(vector<GraphNode>& nodes) {
    vector<bool> visited(nodes.size(), false);
    list<int> order; // 用于存储排序后的节点

    for (int i = 0; i < nodes.size(); ++i) {
        if (!visited[i] && nodes[i].hasOutDegree() == false) {
            dfsHelper(i, nodes, visited, order);
        }
    }

    return order.size() == nodes.size();
}

void dfsHelper(int node, vector<GraphNode>& nodes, vector<bool>& visited, list<int>& order) {
    visited[node] = true;
    for (int neighbor : nodes[node].inDegree) {
        if (!visited[neighbor]) {
            dfsHelper(neighbor, nodes, visited, order);
        }
    }
    order.push_back(node); // 添加到排序序列
}

int main() {
    // 创建图的节点并添加边
    GraphNode g1, g2, g3, g4, g5;
    g1.addEdge({1, 2});
    g1.addEdge({1, 3});
    g2.addEdge({2, 4});
    g3.addEdge({3, 4});
    g4.addEdge({4, 5});

    vector<GraphNode> graph = {g1, g2, g3, g4, g5};

    // 检查是否可以进行拓扑排序
    if (isTopologicalOrder(graph)) {
        cout << "A valid topological sort of the graph is: ";
        for (int node : order) {
            cout << node + 1 << " ";
        }
    } else {
        cout << "The graph contains a cycle and cannot be sorted topologically." << endl;
    }

    return 0;
}

这个代码首先定义了有向边和节点类，然后实现了深度优先搜索辅助函数`dfsHelper`，用于遍历每个节点及其邻居，最后在主函数中创建了一个示例图，并检查它是否能进行拓扑排序。