如何判断一个有向图是否有环C++代码

在C++中，检测有向图是否存在环通常使用深度优先搜索（Depth-First Search, DFS）或拓扑排序算法。这里给出一种基于邻接表实现的DFS方法：

#include <iostream>
#include <vector>
using namespace std;

// 用于标记节点是否被访问过
bool visited[100];

// 检测边 (u, v) 是否存在
bool hasEdge(int u, int v, vector<vector<int>>& adjList) {
    return adjList[u].find(v) != adjList[u].end();
}

// 遍历函数，返回true表示找到环，false表示无环
bool detectCycle(vector<vector<int>>& adjList, int node, int parent = -1) {
    visited[node] = true;
    for (int neighbor : adjList[node]) {
        if (!visited[neighbor]) {
            // 如果邻居未访问过，递归检查
            if (detectCycle(adjList, neighbor, node)) {
                return true;  // 发现环
            }
        } else if (neighbor != parent):  // 如果邻居已访问过且不是父节点，则存在环
            return true;
    }
    return false;
}

int main() {
    vector<vector<int>> adjList;  // 使用邻接表表示图
    // 初始化图结构...

    bool hasCycle = false;
    for (int i = 0; i < numVertices && !hasCycle; ++i) {
        if (!visited[i]) {
            hasCycle = detectCycle(adjList, i);
        }
    }

    if (hasCycle)
        cout << "Graph contains a cycle." << endl;
    else
        cout << "Graph does not contain a cycle." << endl;

    return 0;
}

这个程序首先创建了一个邻接列表 `adjList` 来表示有向图。然后通过 `detectCycle` 函数对每个未访问过的节点进行遍历，如果发现有环则返回 `true`，最后根据 `hasCycle` 的值判断图中是否存在环。