无向连通图环检测DFS算法的O(n)时间复杂度疑问及方案探讨

设计的改进DFS环检测算法步骤 #

• 选取节点current，将其加入visited集合。
• 设置parent = current，current = current.neighbour()，将新的current加入visited。
• 重复步骤2，当遇到已在visited中且不等于parent的节点时，即判定检测到环（例如a→b→c→a是有效环，a→b→a不算环）。

核心疑问点 #

1. 算法漏洞排查：我认为该方案存在潜在漏洞，希望能明确指出问题所在。
2. 时间复杂度分析：若该方案可行，当使用列表存储visited时，每次元素查找耗时O(n)，遍历所有节点的情况下，整体时间复杂度是否为O(n²)？
3. 简化方案失效原因：我曾尝试简化方案——不使用visited列表，仅跟踪起始节点r，每次检查新节点是否等于r（该操作为O(1)），但在r=A的以下图结构中失效：

   C
       / \
   A - B - D
   

   请解释该失效的原因。

内容的提问来源于stack exchange，提问作者anf