图中用深度遍历判断是否有环

在图论中，使用深度优先搜索（Depth First Search, DFS）来判断是否存在环（也称为环路或环），通常涉及到回溯的概念。深度优先搜索的特点是从一个顶点开始，尽可能深地探索分支，如果遇到未访问过的顶点就继续下去，直到无法再深入为止，然后返回上一层。

当你对图中的每个节点进行深度优先遍历时，如果当前节点已经在访问过程中被标记为已访问过（比如使用一个布尔数组或者哈希集合记录已访问节点），这意味着存在一条从起点到这个节点的路径。然后你需要检查从这个节点出发是否能找到回路。一种常见的做法是：

1. 对于每个新访问的节点，将其标记为已访问。
2. 记录下当前节点的父节点。
3. 对当前节点的所有邻居（未访问过的邻接节点）递归地执行DFS。
4. 如果在一个子树中发现一个已经访问过的节点，但是它的父节点不是当前节点，那么说明找到了环（因为存在从起点经过其他节点回到已访问节点的路径）。

以下是一个简单的C++代码示例来演示这种方法：

#include <iostream>
#include <unordered_set> // 使用哈希集存储已访问节点

bool hasCycleUtil(int node, std::vector<int>& adj, std::unordered_set<int>& visited, int parent) {
    visited[node] = true; // 标记当前节点已访问
    for (int neighbor : adj[node]) { // 遍历邻居
        if (!visited[neighbor]) {
            if (hasCycleUtil(neighbor, adj, visited, node)) return true; // 如果找到环，返回true
        } else if (neighbor != parent) { // 如果邻居已被访问但不是父节点，说明有环
            return true;
        }
    }
    return false;
}

// 主函数调用
bool hasCycle(std::vector<std::vector<int>>& adj) {
    std::unordered_set<int> visited(adj.size(), false);
    for (int i = 0; i < adj.size(); ++i) {
        if (!visited[i] && hasCycleUtil(i, adj, visited, -1)) {
            return true;
        }
    }
    return false; // 没有环
}

int main() {
    std::vector<std::vector<int>> adj = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}}; // 示例图的邻接表表示
    if (hasCycle(adj)) {
        std::cout << "Graph contains a cycle.\n";
    } else {
        std::cout << "Graph does not contain a cycle.\n";
    }
    return 0;
}