算法刷题系列（三十八）：图论 DFS——遍历连通分量和结构

算法刷题系列（三十八）：图论 DFS——遍历连通分量和结构

深度优先搜索（DFS）沿一条路径尽可能向前，走不动时回退。它可以遍历图、计算无向图的连通分量，也能通过访问状态识别有向图中的回边和环。不同图类型的“遇到访问过的点”含义不同，不能套用同一个判环条件。

无向图的连通分量

无向图中，从任意尚未访问的顶点启动一次 DFS，就能访问它所在的整个连通分量。外层循环扫过所有顶点，每启动一次就得到一个新的分量。标记要在递归前完成，避免邻接边让搜索重复进入同一顶点。

Java：分量计数与有向环检测

import java.util.List;

public class GraphDfs {
    public static int countUndirectedComponents(List<List<Integer>> graph) {
        boolean[] visited = new boolean[graph.size()];
        int count = 0;
        for (int node = 0; node < graph.size(); node++) {
            if (!visited[node]) {
                count++;
                visitUndirected(graph, node, visited);
            }
        }
        return count;
    }

    private static void visitUndirected(
        List<List<Integer>> graph, int node, boolean[] visited
    ) {
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visitUndirected(graph, neighbor, visited);
            }
        }
    }

    public static boolean hasDirectedCycle(List<List<Integer>> graph) {
        int[] color = new int[graph.size()]; // 0=未访问，1=当前路径，2=已完成
        for (int node = 0; node < graph.size(); node++) {
            if (color[node] == 0 && directedDfs(graph, node, color)) {
                return true;
            }
        }
        return false;
    }

    private static boolean directedDfs(
        List<List<Integer>> graph, int node, int[] color
    ) {
        color[node] = 1;
        for (int neighbor : graph.get(node)) {
            if (color[neighbor] == 1) {
                return true;
            }
            if (color[neighbor] == 0 && directedDfs(graph, neighbor, color)) {
                return true;
            }
        }
        color[node] = 2;
        return false;
    }
}

Python 实现

def count_undirected_components(graph: list[list[int]]) -> int:
    visited = [False] * len(graph)

    def visit(node: int) -> None:
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visit(neighbor)

    count = 0
    for node in range(len(graph)):
        if not visited[node]:
            count += 1
            visit(node)
    return count

def has_directed_cycle(graph: list[list[int]]) -> bool:
    color = [0] * len(graph)  # 0=未访问，1=当前路径，2=已完成

    def visit(node: int) -> bool:
        color[node] = 1
        for neighbor in graph[node]:
            if color[neighbor] == 1:
                return True
            if color[neighbor] == 0 and visit(neighbor):
                return True
        color[node] = 2
        return False

    for node in range(len(graph)):
        if color[node] == 0 and visit(node):
            return True
    return False

assert count_undirected_components([[1], [0], [3], [2], []]) == 3
assert has_directed_cycle([[1], [2], [0]])
assert not has_directed_cycle([[1], [2], []])

判环为什么要区分图类型？

在有向图中，回到当前递归路径上的灰色节点（颜色 1）说明存在有向环；回到已经完成的黑色节点（颜色 2）只说明两条路径汇合，不一定有环。

在无向图中，邻接表会包含父子边的反向边，看到“已访问的邻居”本身不能证明有环：必须排除刚刚经过的那条父边。简单无向图可用 neighbor != parent 判断；含平行边的多重图则应记录边编号，因为同一对端点间的第二条边会构成环。上面用三色 DFS 的判环函数特意处理有向图，不应拿它直接代替无向图判环。

正确性、复杂度与注意事项

外层循环只在未访问顶点上启动遍历，DFS 又恰好沿可达边访问所有邻点，因此每个连通块计数一次。三色算法中，灰色节点表示当前 DFS 路径祖先；沿有向边回到祖先即可构成闭合有向路径。黑色节点不在当前路径上，不足以判环。

邻接表下，DFS 时间为 O(V+E)，访问数组和递归栈总空间 O(V)。递归深度在极长链图中可达 V，可能超过语言栈限制；生产代码或大规模输入可改用显式栈，或用迭代模拟进入/退出状态。

连通分量仅对无向图按通常定义成立；有向图要讨论强连通分量或弱连通分量，需要不同算法或不同建图方式。