有向图中的循环检测
内容提要
介绍了使用DFS和BFS方法检测有向图中循环的步骤和示例。
延伸解读
DFS 检测循环的核心：递归路径标记
DFS 方法使用两个标记：visited 记录已访问节点，dfsVisited 记录当前递归路径上的节点。当遍历邻居时，若邻居未被访问则递归；若邻居已在 dfsVisited 中，说明存在后向边，即循环。递归返回前将当前节点从 dfsVisited 移除，以正确回溯。这种方法能准确检测有向图中的循环，但递归深度受图规模限制。
BFS 检测循环：拓扑排序与入度统计
BFS 方法基于拓扑排序：先计算所有节点的入度，将入度为 0 的节点入队，然后依次出队并减少邻居入度，入度变为 0 时入队。若最终遍历的节点数少于总节点数，则剩余节点无法被拓扑排序，说明图中存在循环。该方法非递归，适合大规模图，但需要额外空间存储入度和队列。
两种方法的对比与选择建议
DFS 实现简单，能直接定位循环路径，但递归可能导致栈溢出；BFS 基于拓扑排序，非递归且能同时得到拓扑序，但需要维护入度表。对于需要检测循环并可能输出拓扑序的场景，BFS 更合适；若只需判断循环存在性且图规模不大，DFS 更直观。两者时间复杂度均为 O(V+E)，空间复杂度也相近。
示例代码的注意事项
示例中节点编号从 1 到 n，但 BFS 的拓扑排序函数假设节点编号从 0 到 n-1，这可能导致节点 0 被遗漏或越界。实际使用时需统一节点编号范围。此外，DFS 的 visited 和 dfsVisited 使用 unordered_map，若节点编号不连续或范围较大，也能正常工作，但需确保所有节点都被遍历到。
Q&A
如何使用DFS方法检测有向图中的循环？
DFS方法通过递归检查节点及其邻居，标记访问状态。如果发现邻居节点已在当前路径中，则表示存在循环。
BFS方法是如何检测有向图中的循环的？
BFS方法通过拓扑排序检测循环，计算每个节点的入度，从入度为0的节点开始遍历，若遍历后节点数量少于总节点数，则存在循环。
在有向图中，如何判断是否存在循环？
可以使用DFS或BFS方法来判断是否存在循环，DFS通过递归检查路径，BFS通过拓扑排序和入度计算。
能否提供一个检测有向图循环的示例？
示例中有4个节点，边为{1, 2}, {2, 3}, {3, 1}，使用DFS和BFS检测后均发现存在循环。
DFS和BFS方法检测循环的主要区别是什么？
DFS使用递归检查路径，而BFS通过拓扑排序和入度计算来检测循环。
在使用BFS方法时，如何处理入度为0的节点？
BFS方法从入度为0的节点开始遍历，逐步减少邻居节点的入度，直到遍历完成。
