小孟的技术笔记

Appearance

遇到图的代码题：分析与解决指南 ​

一、图是什么？ ​

图(Graph)是一种非线性数据结构，由顶点(Vertex) 和边(Edge) 组成，用于表示对象之间的关系。数学表示为 G = (V, E)，其中：

  • V 是顶点集合
  • E 是连接顶点的边集合

图的分类： ​

二、解决什么问题 ​

图结构主要用于解决以下三类问题：

  1. 关系建模问题：社交网络（顶点=用户，边=好友关系）、交通网络（顶点=车站，边=路线）
  2. 路径查找问题：最短路径（导航）、关键路径（项目管理）
  3. 连通性问题：网络连接检测、社交圈分析

三、核心分析方法 ​

遇到图类问题时，采用以下系统分析方法：

1. 问题识别框架 ​

2. 算法选择矩阵 ​

问题类型推荐算法时间复杂度适用场景
遍历所有节点BFS/DFSO(V+E)社交网络好友推荐
最短路径（无权）BFSO(V+E)最少转机路线
最短路径（带权）DijkstraO((V+E)logV)地图导航
最小生成树Prim/KruskalO(ElogV)网络布线优化
拓扑排序Kahn算法O(V+E)任务依赖调度
强连通分量Kosaraju/TarjanO(V+E)社交圈子分析

四、解决步骤 ​

1. 图的表示 ​

邻接表（推荐）：

java
// Java 17+ 语法
List<List<Integer>> graph = new ArrayList<>();

// 添加顶点
IntStream.range(0, n).forEach(i -> graph.add(new ArrayList<>()));

// 添加边 (无向图)
graph.get(u).add(v);
graph.get(v).add(u);

邻接矩阵：

java
int[][] matrix = new int[n][n];
matrix[u][v] = 1; // 无权图
matrix[u][v] = weight; // 带权图

2. 算法实现模板 ​

BFS模板：

java
void bfs(List<List<Integer>> graph, int start) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(start);
    visited[start] = true;
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        // 处理当前节点
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

DFS模板：

java
void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
    visited[node] = true;
    // 处理当前节点
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

3. 特殊问题处理技巧 ​

  • 环检测：DFS中维护递归栈，或使用拓扑排序
  • 最短路径记录：BFS/Dijkstra中维护prev[]数组
  • 连通分量：DFS/BFS计数遍历次数
  • 双向BFS：优化两点间路径搜索

五、应用场景实例 ​

场景1：社交网络好友推荐（BFS应用） ​

java
List<Integer> recommendFriends(List<List<Integer>> graph, int user, int level) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new ArrayDeque<>();
    List<Integer> result = new ArrayList<>();
    int currentLevel = 0;
    
    queue.offer(user);
    visited[user] = true;
    
    while (!queue.isEmpty() && currentLevel <= level) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int node = queue.poll();
            if (currentLevel == level && node != user) {
                result.add(node);
            }
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        currentLevel++;
    }
    return result;
}

场景2：课程安排（拓扑排序） ​

java
// Kahn算法实现拓扑排序
List<Integer> topologicalSort(int numCourses, int[][] prerequisites) {
    // 构建图与入度数组
    List<List<Integer>> graph = new ArrayList<>();
    int[] indegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    
    for (int[] edge : prerequisites) {
        graph.get(edge[1]).add(edge[0]); // edge[1] → edge[0]
        indegree[edge[0]]++;
    }
    
    // BFS初始化
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    
    // 拓扑排序
    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int course = queue.poll();
        result.add(course);
        for (int next : graph.get(course)) {
            if (--indegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    return result.size() == numCourses ? result : Collections.emptyList();
}

六、重要注意事项 ​

  1. 避免死循环：DFS/BFS必须使用visited数组记录访问状态
  2. 稠密图 vs 稀疏图：
    • 稀疏图（边少）：使用邻接表
    • 稠密图（边多）：考虑邻接矩阵
  3. Java特性优化：
    • 使用ArrayDeque代替LinkedList提升队列性能
    • Java 14+ 使用record表示边：record Edge(int to, int weight) {}
  4. 并行处理：Java 8+ 使用并行流处理大型图
    java
    graph.parallelStream().forEach(this::processNode);
  5. 内存优化：对于超大规模图，考虑分块处理或使用磁盘存储

七、总结 ​

解决图类代码题的系统方法：

  1. 识别问题类型：确定是路径、连通性还是排序问题
  2. 选择数据结构：邻接表（通用）或邻接矩阵（稠密图）
  3. 选择算法：
    • 遍历：BFS/DFS
    • 最短路径：BFS（无权）、Dijkstra（带权非负）
    • 依赖排序：拓扑排序
  4. 实现与优化：使用模板代码，注意环检测和状态记录
  5. 边界处理：空图、孤立节点、自环等情况

关键思维：将现实问题抽象为顶点和边的关系，再选择合适的图算法解决。掌握BFS/DFS模板和拓扑排序，能解决80%的图类问题。遇到新问题时，先问："这个问题的顶点是什么？边表示什么关系？"