如何用拓扑排序判断一个有向图是否有环C++代码

判断有向图是否包含环通常通过拓扑排序实现，如果图中存在环，那么无法进行拓扑排序，因为循环会导致顶点的入度永远大于0，无法按照一定的顺序排列出来。以下是使用C++实现拓扑排序的一个简化版示例：

#include <vector>
#include <queue>

// 图结构，邻接表表示法
struct Graph {
    std::vector<int> adj[100]; // 100是个假设的节点数上限
};

bool hasCycle(Graph& g) {
    std::vector<bool> visited(g.size(), false);
    std::queue<int> q;

    for (int i = 0; i < g.size(); ++i) {
        if (!visited[i] && !hasRecursiveloop(g, i, visited)) {
            q.push(i); // 当前节点没有环，加入队列
        }
    }

    return q.empty(); // 如果队列为空，说明图中存在环
}

// 检查是否存在从u指向v的环
bool hasRecursiveloop(const Graph& g, int u, std::vector<bool>& visited) {
    visited[u] = true;
    for (const auto& v : g.adj[u]) {
        if (!visited[v] && hasRecursiveloop(g, v, visited)) { // 发现从u到v的环
            return true;
        } else if (visited[v]) { // 已经访问过v，说明有环
            return true;
        }
    }
    visited[u] = false; // 出栈后还原状态
    return false;
}

// 使用示例
int main() {
    Graph g;
    // 初始化你的有向图...
    if (hasCycle(g)) {
        std::cout << "Graph contains a cycle." << std::endl;
    } else {
        std::cout << "Graph is acyclic." << std::endl;
    }
    return 0;
}

这个代码首先初始化了一个`visited`数组来跟踪每个节点是否被访问过，并使用一个队列来存储未处理的节点。`hasRecursiveloop`函数递归地检查每个节点的邻居，如果发现环则返回`true`。如果没有环，整个图会被成功排序，然后`hasCycle`函数将返回`false`。