跳到主要内容

图的遍历与拓扑排序

图的遍历是按照某种规则访问图中所有顶点的过程，是图算法的基础。最基本的两种遍历算法是深度优先搜索（DFS）和广度优先搜索（BFS），它们不仅是图论的核心操作，也是许多复杂图算法的基石。

图的表示方式​

在讨论遍历算法之前，需要了解图的常见表示方式：

邻接矩阵​

使用二维数组表示，matrix[i][j] 表示顶点 i 到顶点 j 是否有边。

// 邻接矩阵表示
int[][] graph = {
    {0, 1, 1, 0},  // 顶点0连接到顶点1和2
    {1, 0, 0, 1},  // 顶点1连接到顶点0和3
    {1, 0, 0, 1},  // 顶点2连接到顶点0和3
    {0, 1, 1, 0}   // 顶点3连接到顶点1和2
};
  • 空间复杂度：O(V2)O(V^2)
  • 查询边是否存在：O(1)O(1)
  • 遍历邻居：O(V)O(V)
  • 适合稠密图

邻接表​

使用数组或哈希表存储，每个顶点维护一个邻居列表。

// 邻接表表示
List<List<Integer>> graph = new ArrayList<>();
// 初始化
for (int i = 0; i < n; i++) {
    graph.add(new ArrayList<>());
}
// 添加边
graph.get(0).add(1);  // 顶点0连接到顶点1
graph.get(0).add(2);  // 顶点0连接到顶点2
  • 空间复杂度：O(V+E)O(V + E)
  • 查询边是否存在：O(degree(v))O(degree(v))
  • 遍历邻居：O(degree(v))O(degree(v))
  • 适合稀疏图（大多数实际应用）

深度优先搜索（DFS）​

深度优先搜索（Depth-First Search）是一种"一条路走到黑"的遍历策略：从起点出发，沿着一条路径尽可能深入，直到无法继续，然后回溯到上一个分叉点继续探索。

核心思想​

DFS 的核心是递归或栈：先访问当前节点，然后对每个未访问的邻居递归调用 DFS。由于使用栈（或递归调用栈），DFS 会沿着一条路径尽可能深入。

算法步骤​

  1. 从起始顶点开始，标记为已访问
  2. 对当前顶点的每个未访问邻居，递归执行 DFS
  3. 当所有邻居都已访问，回溯到上一顶点

代码实现​

递归实现：

public void dfs(int[][] graph, int start) {
    int n = graph.length;
    boolean[] visited = new boolean[n];
    dfsHelper(graph, start, visited);
}

private void dfsHelper(int[][] graph, int vertex, boolean[] visited) {
    // 标记当前顶点为已访问
    visited[vertex] = true;
    System.out.println("访问顶点: " + vertex);
    
    // 遍历所有邻居
    for (int neighbor = 0; neighbor < graph.length; neighbor++) {
        // 如果有边且邻居未访问
        if (graph[vertex][neighbor] == 1 && !visited[neighbor]) {
            dfsHelper(graph, neighbor, visited);
        }
    }
}

邻接表版本：

public void dfs(List<List<Integer>> graph, int start) {
    int n = graph.size();
    boolean[] visited = new boolean[n];
    dfsHelper(graph, start, visited);
}

private void dfsHelper(List<List<Integer>> graph, int vertex, boolean[] visited) {
    visited[vertex] = true;
    System.out.println("访问顶点: " + vertex);
    
    // 遍历所有邻居
    for (int neighbor : graph.get(vertex)) {
        if (!visited[neighbor]) {
            dfsHelper(graph, neighbor, visited);
        }
    }
}

迭代实现（使用显式栈）：

public void dfsIterative(List<List<Integer>> graph, int start) {
    int n = graph.size();
    boolean[] visited = new boolean[n];
    Stack<Integer> stack = new Stack<>();
    
    stack.push(start);
    
    while (!stack.isEmpty()) {
        int vertex = stack.pop();
        
        // 可能多次入栈，需要检查是否已访问
        if (visited[vertex]) continue;
        
        visited[vertex] = true;
        System.out.println("访问顶点: " + vertex);
        
        // 将未访问的邻居入栈（逆序入栈保证顺序正确）
        List<Integer> neighbors = graph.get(vertex);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            int neighbor = neighbors.get(i);
            if (!visited[neighbor]) {
                stack.push(neighbor);
            }
        }
    }
}

时间复杂度分析​

图表示方式时间复杂度说明
邻接表O(V+E)O(V + E)每个顶点和边访问一次
邻接矩阵O(V2)O(V^2)每个顶点检查所有可能的邻居

空间复杂度：O(V)O(V)（visited 数组 + 递归栈/显式栈）

DFS 的应用场景​

1. 检测连通分量​

无向图中，从任意一个未访问顶点开始 DFS，能到达的所有顶点构成一个连通分量。

public int countConnectedComponents(List<List<Integer>> graph) {
    int n = graph.size();
    boolean[] visited = new boolean[n];
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfsHelper(graph, i, visited);
            count++;  // 每次DFS完成，找到一个连通分量
        }
    }
    
    return count;
}

2. 检测环​

在有向图中检测环：维护一个递归栈，如果在 DFS 过程中遇到一个已在递归栈中的顶点，则存在环。

public boolean hasCycle(List<List<Integer>> graph) {
    int n = graph.size();
    int[] status = new int[n];  // 0: 未访问, 1: 正在访问, 2: 已完成
    
    for (int i = 0; i < n; i++) {
        if (status[i] == 0) {
            if (dfsCycle(graph, i, status)) {
                return true;
            }
        }
    }
    return false;
}

private boolean dfsCycle(List<List<Integer>> graph, int vertex, int[] status) {
    status[vertex] = 1;  // 标记为正在访问
    
    for (int neighbor : graph.get(vertex)) {
        if (status[neighbor] == 1) {
            // 邻居正在被访问，说明有环
            return true;
        }
        if (status[neighbor] == 0) {
            if (dfsCycle(graph, neighbor, status)) {
                return true;
            }
        }
    }
    
    status[vertex] = 2;  // 标记为已完成
    return false;
}

3. 拓扑排序（DFS 方法）​

DFS 的逆后序遍历就是拓扑排序的一种。详见后文拓扑排序章节。

4. 路径查找​

查找从起点到终点的路径：

public List<Integer> findPath(List<List<Integer>> graph, int start, int end) {
    int n = graph.size();
    boolean[] visited = new boolean[n];
    List<Integer> path = new ArrayList<>();
    
    if (dfsPath(graph, start, end, visited, path)) {
        return path;
    }
    return Collections.emptyList();  // 没有路径
}

private boolean dfsPath(List<List<Integer>> graph, int current, int end, 
                        boolean[] visited, List<Integer> path) {
    visited[current] = true;
    path.add(current);
    
    if (current == end) {
        return true;  // 找到终点
    }
    
    for (int neighbor : graph.get(current)) {
        if (!visited[neighbor]) {
            if (dfsPath(graph, neighbor, end, visited, path)) {
                return true;
            }
        }
    }
    
    // 回溯
    path.remove(path.size() - 1);
    return false;
}

广度优先搜索（BFS）​

广度优先搜索（Breadth-First Search）是一种"层层推进"的遍历策略：由内而外、逐层访问顶点，先访问距离起点为 1 的所有顶点，再访问距离为 2 的所有顶点，以此类推。

核心思想​

BFS 的核心是队列：先访问当前顶点，将其所有未访问的邻居加入队列。这保证了按"距离"的顺序访问顶点。

算法步骤​

  1. 将起始顶点加入队列
  2. 从队列取出一个顶点，标记为已访问
  3. 将该顶点的所有未访问邻居加入队列
  4. 重复步骤 2-3 直到队列为空

代码实现​

public void bfs(List<List<Integer>> graph, int start) {
    int n = graph.size();
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    
    visited[start] = true;
    queue.offer(start);
    
    while (!queue.isEmpty()) {
        int vertex = queue.poll();
        System.out.println("访问顶点: " + vertex);
        
        for (int neighbor : graph.get(vertex)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;  // 标记后再入队，避免重复入队
                queue.offer(neighbor);
            }
        }
    }
}

时间复杂度分析​

图表示方式时间复杂度说明
邻接表O(V+E)O(V + E)每个顶点和边访问一次
邻接矩阵O(V2)O(V^2)每个顶点检查所有可能的邻居

空间复杂度：O(V)O(V)（visited 数组 + 队列）

BFS 的应用场景​

1. 无权图的最短路径​

BFS 天然适合求无权图的最短路径：第一次到达某个顶点时，经过的边数就是最短距离。

public int shortestPath(List<List<Integer>> graph, int start, int end) {
    if (start == end) return 0;
    
    int n = graph.size();
    int[] distance = new int[n];
    Arrays.fill(distance, -1);  // -1 表示未访问
    
    Queue<Integer> queue = new LinkedList<>();
    distance[start] = 0;
    queue.offer(start);
    
    while (!queue.isEmpty()) {
        int vertex = queue.poll();
        
        for (int neighbor : graph.get(vertex)) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[vertex] + 1;
                
                if (neighbor == end) {
                    return distance[neighbor];  // 找到最短路径
                }
                
                queue.offer(neighbor);
            }
        }
    }
    
    return -1;  // 没有路径
}

2. 层级遍历​

当需要按层级处理顶点时（如输出每层的顶点）：

public List<List<Integer>> levelOrder(List<List<Integer>> graph, int start) {
    List<List<Integer>> result = new ArrayList<>();
    int n = graph.size();
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    
    visited[start] = true;
    queue.offer(start);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            int vertex = queue.poll();
            level.add(vertex);
            
            for (int neighbor : graph.get(vertex)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        
        result.add(level);
    }
    
    return result;
}

3. 判断二分图​

使用 BFS 对图进行二染色：

public boolean isBipartite(List<List<Integer>> graph) {
    int n = graph.size();
    int[] color = new int[n];  // 0: 未染色, 1: 颜色A, -1: 颜色B
    
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            if (!bfsBipartite(graph, i, color)) {
                return false;
            }
        }
    }
    return true;
}

private boolean bfsBipartite(List<List<Integer>> graph, int start, int[] color) {
    Queue<Integer> queue = new LinkedList<>();
    color[start] = 1;
    queue.offer(start);
    
    while (!queue.isEmpty()) {
        int vertex = queue.poll();
        
        for (int neighbor : graph.get(vertex)) {
            if (color[neighbor] == 0) {
                // 染成相反颜色
                color[neighbor] = -color[vertex];
                queue.offer(neighbor);
            } else if (color[neighbor] == color[vertex]) {
                // 相邻顶点颜色相同，不是二分图
                return false;
            }
        }
    }
    return true;
}

DFS vs BFS 对比​

特性DFSBFS
数据结构栈（递归或显式栈）队列
空间复杂度O(h)O(h)，h 为深度O(w)O(w)，w 为最大宽度
最短路径不保证（除非回溯）天然保证（无权图）
适用场景路径查找、连通性、环检测最短路径、层级遍历
实现复杂度递归简洁迭代直观

选择建议：

  • 需要最短路径 → BFS
  • 图的深度很大、宽度很小 → BFS 空间更优
  • 图的宽度很大、深度很小 → DFS 空间更优
  • 需要遍历所有路径 → DFS
  • 层级相关的问题 → BFS

拓扑排序​

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

应用场景​

拓扑排序广泛应用于有依赖关系的调度问题：

  • 课程安排：课程 A 是课程 B 的先修课，确定课程顺序
  • 编译依赖：模块 A 依赖模块 B，确定编译顺序
  • 任务调度：任务 A 必须在任务 B 之前完成

前提条件​

拓扑排序存在的充要条件是图是有向无环图（DAG）。如果图中存在环，则不存在拓扑排序。

实现方法一：Kahn 算法（BFS）​

Kahn 算法基于入度的概念，是一种 BFS 方法。

核心思想：每次选择入度为 0 的顶点加入排序结果，然后移除该顶点及其出边，更新邻居的入度，继续这个过程。

算法步骤：

  1. 计算所有顶点的入度
  2. 将所有入度为 0 的顶点加入队列
  3. 从队列取出一个顶点，加入排序结果
  4. 将该顶点所有邻居的入度减 1
  5. 如果某邻居入度变为 0，加入队列
  6. 重复步骤 3-5 直到队列为空

代码实现：

public int[] topologicalSortKahn(List<List<Integer>> graph) {
    int n = graph.size();
    int[] inDegree = new int[n];
    
    // 计算所有顶点的入度
    for (int i = 0; i < n; i++) {
        for (int neighbor : graph.get(i)) {
            inDegree[neighbor]++;
        }
    }
    
    // 将入度为 0 的顶点加入队列
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    int[] result = new int[n];
    int index = 0;
    
    while (!queue.isEmpty()) {
        int vertex = queue.poll();
        result[index++] = vertex;
        
        // 更新邻居的入度
        for (int neighbor : graph.get(vertex)) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }
    
    // 如果排序结果不足 n 个，说明有环
    if (index != n) {
        throw new IllegalArgumentException("图中存在环，无法进行拓扑排序");
    }
    
    return result;
}

时间复杂度：O(V+E)O(V + E) 空间复杂度：O(V)O(V)

实现方法二：DFS 逆后序​

DFS 方法利用递归完成时间：顶点的完成时间越晚，越应该排在前面。

核心思想：在 DFS 过程中，顶点遍历完所有邻居后才"完成"。完成时间越晚的顶点，在拓扑排序中越靠前。

算法步骤：

  1. 对每个未访问顶点执行 DFS
  2. 在顶点的所有邻居都访问完毕后，将顶点加入结果列表
  3. 最后将结果列表逆序

代码实现：

public int[] topologicalSortDFS(List<List<Integer>> graph) {
    int n = graph.size();
    int[] status = new int[n];  // 0: 未访问, 1: 正在访问, 2: 已完成
    LinkedList<Integer> result = new LinkedList<>();
    
    for (int i = 0; i < n; i++) {
        if (status[i] == 0) {
            if (!dfsTopo(graph, i, status, result)) {
                throw new IllegalArgumentException("图中存在环，无法进行拓扑排序");
            }
        }
    }
    
    return result.stream().mapToInt(i -> i).toArray();
}

private boolean dfsTopo(List<List<Integer>> graph, int vertex, 
                        int[] status, LinkedList<Integer> result) {
    status[vertex] = 1;  // 标记为正在访问
    
    for (int neighbor : graph.get(vertex)) {
        if (status[neighbor] == 1) {
            // 遇到正在访问的顶点，说明有环
            return false;
        }
        if (status[neighbor] == 0) {
            if (!dfsTopo(graph, neighbor, status, result)) {
                return false;
            }
        }
    }
    
    status[vertex] = 2;  // 标记为已完成
    result.addFirst(vertex);  // 逆序添加，或最后反转
    return true;
}

时间复杂度：O(V+E)O(V + E) 空间复杂度：O(V)O(V)

两种方法对比​

特性Kahn 算法DFS 方法
检测环结果长度小于顶点数遇到正在访问的顶点
遍历方式BFSDFS
空间队列 + 入度数组递归栈 + 结果列表
直观性入度概念直观逆后序需要理解

拓扑排序唯一性​

拓扑排序不一定唯一。当存在多个入度为 0 的顶点时，选择顺序不同会得到不同的拓扑排序。

例如，对于图 A → C, B → C，两种拓扑排序都是合法的：

  • [A, B, C]
  • [B, A, C]

综合示例：课程表问题（LeetCode 207/210）​

判断能否完成所有课程​

给定 n 门课程和先修关系列表，判断能否完成所有课程。

分析：这是一个拓扑排序问题。如果存在环，则无法完成。

public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 构建图
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    int[] inDegree = new int[numCourses];
    
    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);  // pre[1] -> pre[0]
        inDegree[pre[0]]++;
    }
    
    // Kahn 算法
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    int count = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        
        for (int next : graph.get(course)) {
            inDegree[next]--;
            if (inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    
    return count == numCourses;
}

返回课程学习顺序​

不仅判断能否完成，还要返回一种合法的学习顺序。

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    int[] inDegree = new int[numCourses];
    
    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);
        inDegree[pre[0]]++;
    }
    
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    int[] result = new int[numCourses];
    int index = 0;
    
    while (!queue.isEmpty()) {
        int course = queue.poll();
        result[index++] = course;
        
        for (int next : graph.get(course)) {
            inDegree[next]--;
            if (inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    
    return index == numCourses ? result : new int[0];
}

小结​

图遍历算法是图论的基础，掌握 DFS 和 BFS 是学习高级图算法的前提：

DFS 要点：

  • 使用递归或栈实现
  • 适合路径查找、连通性检测、环检测
  • 空间与图深度相关

BFS 要点：

  • 使用队列实现
  • 天然适合求无权图最短路径
  • 空间与图宽度相关

拓扑排序要点：

  • 仅适用于 DAG
  • Kahn 算法（BFS）直观易懂
  • DFS 方法基于逆后序
  • 可用于检测环

练习​

DFS 相关：

  1. LeetCode 200：岛屿数量
  2. LeetCode 130：被围绕的区域
  3. LeetCode 133：克隆图
  4. LeetCode 494：目标和

BFS 相关： 5. LeetCode 102：二叉树的层序遍历 6. LeetCode 127：单词接龙 7. LeetCode 785：判断二分图 8. LeetCode 994：腐烂的橘子

拓扑排序： 9. LeetCode 207：课程表 10. LeetCode 210：课程表 II 11. LeetCode 310：最小高度树 12. LeetCode 802：找到最终的安全状态