为何检测图中环时优先使用DFS而非BFS？

• 路径追踪更直观
  DFS的核心是沿着单一路径深度遍历，直到走不通再回溯。这种特性让它能天然追踪当前正在遍历的路径（通过递归栈或手动维护的栈）。不管是无向图还是有向图，只要遍历中遇到一个已经在当前路径栈里的节点，就能直接判定存在环——无向图只需排除父节点，有向图无需额外排除，逻辑简单直接。

• 空间效率更优
  DFS的空间开销主要来自遍历栈的深度，在多数实际场景（比如稀疏图、链式结构的图）中，栈的深度远小于BFS队列的大小。即使是最坏情况，两者空间复杂度都是O(n)，但DFS递归实现时无需手动维护队列，内存开销更紧凑，代码也更简洁。

• 环路径定位更便捷
  如果需要找出环的具体路径，DFS的栈本身就保存了当前遍历的完整路径，一旦检测到环，直接从栈中提取环的起点到当前节点的片段即可。而BFS要实现同样的功能，需要额外维护每个节点的前驱节点，再通过反向回溯来拼接路径，步骤繁琐得多。

• 实现复杂度更低
  递归版的DFS环检测代码非常简洁，几行就能完成核心逻辑。比如无向图的环检测：

def has_cycle(graph):
    visited = set()
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False
    for node in graph:
        if node not in visited:
            if dfs(node, -1):
                return True
    return False

相比之下，BFS需要维护队列和父节点映射，代码逻辑更复杂，容易出错。

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