C++ 图中环检测算法可视化 (DFS)

C++ 实现 (DFS)

核心思想与状态

#include < iostream > #include < vector > #include < unordered_map > #include < unordered_set > #include < algorithm > using namespace std; // 表示图中节点的状态 enum class NodeState { UNVISITED, // 0: 未访问 (白色/灰色) VISITING, // 1: 正在访问 (在当前DFS递归栈上, 灰色/蓝色) VISITED // 2: 已访问完成 (其所有邻居都已访问完毕, 黑色/绿色) };

图类定义

class Graph { private: // 使用邻接表表示有向图 unordered_map> adj; // 存储图中所有节点 (方便初始化状态) unordered_set nodes; public: // 添加一条从 from 到 to 的有向边 void addEdge(int from, int to) { adj[from].push_back(to); nodes.insert(from); nodes.insert(to); } // ... (其他图操作如获取节点等) };

DFS 环检测核心递归函数

private: // 递归的DFS辅助函数, 用于检测环 // state: 记录每个节点当前的状态 (UNVISITED, VISITING, VISITED) bool detectCycleUtil(int node, unordered_map& state) { // 1. 将当前节点标记为"正在访问" state[node] = NodeState::VISITING; // 2. 遍历当前节点的所有邻居 if (adj.count(node)) { // 确保节点在邻接表中有记录 for (int neighbor : adj[node]) { // 获取邻居的状态 NodeState neighborState = state.count(neighbor) ? state[neighbor] : NodeState::UNVISITED; // 情况 A: 如果邻居节点从未访问过 if (neighborState == NodeState::UNVISITED) { // 递归地对邻居进行DFS if (detectCycleUtil(neighbor, state)) { return true; // 在子树中发现了环, 直接返回 true } } // 情况 B: 如果邻居节点正在被访问 (即在当前递归栈中) else if (neighborState == NodeState::VISITING) { // 找到了一个返祖边 (back edge), 说明形成了环 return true; } // 情况 C: 如果邻居节点已访问完成 (VISITED), // 说明从那个邻居出发的路径已经探索完毕且没有发现指向当前路径的环, // 因此可以安全地忽略它, 继续检查下一个邻居。 } } // 3. 当前节点的所有邻居都已处理完毕 (没有从这条路径发现环) // 将当前节点标记为"已访问完成" state[node] = NodeState::VISITED; return false; // 从当前节点出发的路径未发现环 }

主检测函数与查找环路径

public: // 检查图中是否存在环 (主函数) bool hasCycle() { // 初始化所有节点状态为未访问 unordered_map state; for (int node : nodes) { state[node] = NodeState::UNVISITED; } // 遍历图中所有节点 for (int node : nodes) { // 如果节点尚未访问, 则从该节点开始进行DFS if (state[node] == NodeState::UNVISITED) { if (detectCycleUtil(node, state)) { return true; // 只要在一个DFS分支中发现环, 就说明图中存在环 } } } return false; // 遍历完所有节点及其可达路径, 未发现环 } // (可选) 查找并返回图中的一个环路径 (如果存在) // findCyclePathUtil 与 detectCycleUtil 类似, 但需要记录路径 path // 当发现 neighborState == VISITING 时, 从 path 中提取环 vector findCycle() { // ... 实现查找具体环路径的逻辑 ... unordered_map state; vector path; // 当前DFS路径 vector cycle; // 存储找到的环 for (int node : nodes) { state[node] = NodeState::UNVISITED; } for (int node : nodes) { if (state[node] == NodeState::UNVISITED) { path.clear(); if (findCyclePathUtil(node, state, path, cycle)) { return cycle; } } } return {}; // 未找到环 } private: bool findCyclePathUtil(int node, unordered_map& state, vector& path, vector& cycle) { state[node] = NodeState::VISITING; path.push_back(node); if (adj.count(node)) { for (int neighbor : adj[node]) { NodeState neighborState = state.count(neighbor) ? state[neighbor] : NodeState::UNVISITED; if (neighborState == NodeState::UNVISITED) { if (findCyclePathUtil(neighbor, state, path, cycle)) { return true; } } else if (neighborState == NodeState::VISITING) { auto it = find(path.begin(), path.end(), neighbor); if (it != path.end()) { cycle.assign(it, path.end()); // cycle.push_back(neighbor); // 不需要重复添加起点 return true; } } } } path.pop_back(); // 回溯 state[node] = NodeState::VISITED; return false; } }; // End of Graph class

主函数示例 (main)

int main() { Graph g; // 添加边构建一个有环的图 g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(2, 0); // 环: 0 -> 1 -> 2 -> 0 g.addEdge(2, 3); g.addEdge(3, 4); // g.addEdge(4, 1); // 可以取消注释这条边来创建另一个环 if (g.hasCycle()) { cout << "图中存在环。\n"; vector cycle = g.findCycle(); if (!cycle.empty()) { cout << "找到一个环: "; for (size_t i = 0; i < cycle.size(); ++i) { cout << cycle[i] << (i == cycle.size() - 1 ? "" : " -> "); } cout << " -> " << cycle[0] << endl; // 显式地回到起点 } } else { cout << "图中不存在环。\n"; } return 0; }

图中环检测算法 (DFS)

在图论中，环检测 (Cycle Detection) 是一个基础且重要的问题，用于判断一个有向图或无向图中是否存在环（也称为回路或循环）。图中的环是指一条路径，其起点和终点是同一个顶点。

本页面主要展示了基于深度优先搜索 (DFS) 的有向图环检测算法。该算法的核心思想是利用节点在 DFS 过程中的三种状态来判断是否存在"返祖边"（即指向当前 DFS 路径上已访问节点的边）。

对图中的每个尚未访问的节点，启动一次深度优先遍历。
在遍历过程中，维护每个节点的访问状态：
- 未访问 (UNVISITED): 节点从未被访问过。
- 正在访问 (VISITING): 节点已被访问，且其邻接点的探索尚未全部完成（即该节点在当前的 DFS 递归栈上）。
- 已访问 (VISITED): 节点及其所有邻居都已被完全探索完毕（即该节点已从 DFS 递归栈中弹出）。
当从节点 u 访问其邻居 v 时：
- 如果 v 是 未访问 状态，则递归地对 v 进行 DFS。若在 v 的子树中检测到环，则图存在环。
- 如果 v 是 正在访问 状态，则找到了一条从当前 DFS 路径指向路径中更早节点的边（返祖边），形成了一个环。
- 如果 v 是 已访问 状态，说明 v 及其子树已被完全探索过且未发现指向当前路径的环，可以安全地忽略。
如果遍历完所有节点都没有遇到指向"正在访问"状态节点的情况，则图中无环。
检测到的环的组成部分将用红色/粉红色标记。

对于无向图： 使用 DFS 检测无向图中的环时，需要额外注意。在从节点 u 访问邻居 v 时，如果 v 是"正在访问"状态，我们必须确保 v 不是 u 的直接父节点（即启动对 u 的 DFS 的那个节点）。否则，对于无向边 (u, v)，从 u 到 v 再立即回到 u 会被错误地判断为环。通常在 DFS 函数中传递父节点 ID 来进行判断：if (neighbor != parent)。

该算法对于有向图和无向图的时间复杂度均为 O(V + E)，其中 V 是顶点数量，E 是边的数量。

提示：点击左上角的 ☰ 按钮可以查看 C++ 代码实现。

算法可视化交互

算法详细步骤:

请在画布上添加节点和边，或加载示例图。

图例:

未访问

正在访问

已访问

环中节点/边

图中环检测算法 (DFS)

算法可视化交互

使用说明