跳到主要内容

图的遍历与拓扑排序

图的遍历是按照某种规则访问图中所有顶点的过程。最基本的两种算法是深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索 DFS​

从起点出发，沿着一条路径尽可能深入，直到无法继续，然后回溯到上一个分叉点继续探索。

核心思想​

  • 使用 递归 或 栈 实现。
  • 需要 visited 数组记录已访问顶点。

应用​

  1. 检测连通分量：遍历过程中计数。
  2. 拓扑排序：利用 DFS 的逆后序。
  3. 检测环：维护递归栈。
public void dfs(int vertex, boolean[] visited) {
    visited[vertex] = true;
    // 访问操作...
    for (int neighbor : graph.getNeighbors(vertex)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}

广度优先搜索 BFS​

由内而外、逐层访问顶点。先访问距离起点为 1 的，再访问距离为 2 的。

核心思想​

  • 使用 队列 实现。
  • 适合求解 无权图的最短路径。
public void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[V];
    visited[start] = true;
    queue.offer(start);
    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int next : graph.getNeighbors(v)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

拓扑排序 Topological Sort​

拓扑排序是对有向无环图（DAG）顶点的线性排序，使得对于每一条有向边 (u,v)(u, v)，uu 都在 vv 之前。

实现方式​

  1. Kahn 算法 (入度表法)：每次取入度为 0 的顶点入队，然后将其邻接顶点的入度减 1。
  2. DFS 逆后序。

练习​

  1. LeetCode 200：岛屿数量 (DFS/BFS)
  2. LeetCode 207/210：课程表 (拓扑排序)
  3. LeetCode 133：克隆图
  4. LeetCode 785：判断二分图