c++拓扑排序 代码实现

C++中的拓扑排序通常用于有向无环图(DAG, Directed Acyclic Graph)中，它将图中所有的节点按照它们的依赖关系排成线性的顺序。这种排序可以帮助我们确定任务的执行顺序，例如在一个任务图中，先完成的任务可以放在前面。

下面是一个简单的C++代码实现，使用邻接表来表示图，并使用深度优先搜索(DFS)进行排序：

#include <iostream>
#include <vector>
#include <list>

using namespace std;

// 图节点结构体
struct Node {
    int id;
    vector<int> adj; // 存储邻居节点
};

// 检查图是否强连通分量
bool isCyclic(Node* node, list<Node*> &visited, list<Node*>& result) {
    visited.push_back(node);
    bool hasCycle = false;

    for (int neighbor : node->adj) {
        if (visited.end() == find(visited.begin(), visited.end(), static_cast<Node*>(neighbor))) {
            hasCycle |= isCyclic(neighbor, visited, result);
        }
    }

    if (!hasCycle) {
        result.push_back(node);
        return false;
    } else {
        visited.pop_back();
        return true;
    }
}

// 拓扑排序
void topologicalSort(vector<Node>& graph) {
    int n = graph.size();
    list<Node*> nodes(n), result;

    // 初始化所有节点为未访问状态
    for (int i = 0; i < n; ++i)
        nodes[i] = &graph[i];

    // 对每个节点，如果发现没有从它指向的边，将其加入结果列表
    for (Node* node : nodes) {
        if (isCyclic(node, list<Node*>(), result)) { // 如果存在环，则无法排序
            cout << "Graph contains a cycle and is not a DAG." << endl;
            return;
        }
    }

    // 将节点按顺序添加到结果列表
    while (!result.empty()) {
        Node* current = result.front();
        result.pop_front();
        cout << current->id << " ";
        for (int neighbor : current->adj)
            nodes.erase(find(nodes.begin(), nodes.end(), static_cast<Node*>(neighbor)));
    }
}

// 示例图构造
void buildExampleGraph(vector<Node>& graph) {
    Node node1{1, {2}};
    Node node2{2, {3}};
    Node node3{3, {}};
    graph.push_back(node1);
    graph.push_back(node2);
    graph.push_back(node3);
}

int main() {
    vector<Node> graph;
    buildExampleGraph(graph); // 假设这里构造了一个示例图

    cout << "Topological sort of the example graph: ";
    topologicalSort(graph);
    cout << endl;

    return 0;
}