深度优先算法（DFS）可以用于判断有向图是否存在回路，具体方法如下：

一、核心思路

通过DFS遍历图时，利用节点访问状态（未访问、访问中、已访问）检测反向边（即从子节点指向父节点的边），从而判断是否存在回路。

二、具体实现步骤

1. 初始化状态

   将所有节点标记为“未访问”，创建一个递归栈用于记录当前路径上的节点。

2. 遍历节点

   • 从任意未访问节点出发，标记为“访问中”并递归访问其邻接节点。

   • 若邻接节点已处于“访问中”状态，说明存在反向边，即存在回路。

   • 若邻接节点未访问，则继续递归。

3. 完成遍历

   当节点所有邻接节点均访问完毕后，标记为“已访问”，并继续处理下一个未访问节点。

三、代码示例（C语言）

bool dfs_has_cycle(Node* node) {
    node->in_process = true;
    for (int i = 0; i < adj_count; ++i) {
        Node* neighbor = node->adj_list[i];
        if (!neighbor->visited) {
            if (dfs_has_cycle(neighbor)) {
                return true;
            }
        } else if (neighbor->in_process) {
            return true;
        }
    }
    node->in_process = false;
    return false;
}

四、注意事项

• 适用性 ：该方法适用于有向图，且需检测所有连通分量（非连通图需分别处理）。

• 时间复杂度 ：O（V+E），与DFS遍历时间复杂度一致。

五、对比其他方法

拓扑排序也可用于检测回路，但需在排序完成后检查剩余未排序节点（存在回路时必有未排序节点）。DFS通过检测反向边实现，无需额外排序步骤。