1. 概述
在本篇教程中，我们将学习如何使用 深度优先搜索（DFS） 来检测 无向图中的环（Cycle）。
2. 什么是图（Graph）？
图是一种数据结构，由一组顶点（Vertex）和连接这些顶点的边（Edge）组成。
我们可以将图表示为 G = (V, E)，其中：
V是顶点集合E是边集合，每条边连接两个顶点
例如，如果顶点 v1 和 v3 之间有一条边，我们就称它们是相邻的（adjacent），也可以说它们是彼此的邻居（neighbor）。
图可以分为两类：
✅ 有向图（Directed Graph）：边具有方向性。例如 (v1, v2) 和 (v2, v1) 是不同的。
✅ 无向图（Undirected Graph）：边是双向的。例如 (v1, v2) 等同于 (v2, v1)。
3. 什么是环（Cycle）？
在图论中，从某个顶点出发，最终又能回到该顶点的路径 被称为一个环。
检测图中是否存在环是计算机科学中的一个重要课题。对于无向图，检测环的时间复杂度为 Ω(n)。
下图展示了一个无向图中的环：节点 3-4-5-6-3 构成了一个环。
4. 环检测算法
我们使用 深度优先搜索（DFS） 来检测无向图中是否存在环。
4.1 DFS 简要回顾
DFS 是一种常用的图遍历算法。它的基本思路是：
- 从某个顶点开始，将其压入栈中
- 如果该顶点有未访问的邻居，选择一个压入栈中，继续遍历
- 当没有未访问的邻居时，弹出栈，回溯到上一个顶点
4.2 检测环的关键逻辑
在 DFS 遍历过程中，如果当前顶点 v 有一个已访问的邻居 u，并且：
u就是v自己（自环），或者u不是v的父节点（parent）
那么说明图中存在一个环。
4.3 算法伪代码
下面是检测环的伪代码：
algorithm detectcycle(v):
mark(v) = visited
for each neighbor u of v:
if u is visited:
if u == v or u != parent(v):
return true
else if detectcycle(u) returns true:
return true
return false
我们可以通过调用 detectcycle(v0) 来检测整个图中是否存在环，其中 v0 是任意一个起始顶点。
5. 总结
本篇教程中，我们介绍了如何使用深度优先搜索（DFS）来检测无向图中的环。核心思想是：在 DFS 遍历过程中，如果发现一个已访问过的节点，并且它不是当前节点的父节点，就说明存在环。
这种方法的时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数，适用于大多数实际场景。