图论专题导读

图论是算法版图里最"工程化"的专题：它的代码套路性极强，但每道题都绕不开两件事——把图存起来和把图遍历完。这两件基本功扎实了，岛屿、并查集、最短路都是在它们上面叠加策略而已。

一、图的两种存法

同一个图可以用两种结构存储，以一个 4 节点 4 条边的图为例：

节点：1 2 3 4
边：(1,2) (1,3) (3,4) (2,4)     （无向图）

邻接矩阵（n×n 二维数组）          邻接表（List<Integer>[] 数组）
     1  2  3  4                  1 → [2, 3]
  1 [0, 1, 1, 0]                 2 → [1, 4]
  2 [1, 0, 0, 1]                 3 → [1, 4]
  3 [1, 0, 0, 1]                 4 → [2, 3]
  4 [0, 1, 1, 0]

维度	邻接矩阵	邻接表
空间	O(n²)，与边数无关	O(n + m)，边多边少都省
查边 (u,v) 是否存在	O(1) 直查	O(deg(u)) 需遍历链
遍历 u 的邻居	O(n) 扫一行	O(deg(u)) 直接取
适用场景	稠密图、要快速判边	稀疏图、要快速扩邻居
Java 实现	`int[][] grid`	`List<List<Integer>>` 或数组套 ArrayList

经验法则：n ≤ 几百用矩阵，n 上千用邻接表；网格类题目（岛屿）天然就是矩阵，不用再建图。

二、ACM 输入模式：读入模板

LeetCode 核心代码模式会把图直接作为函数参数传入，但 ACM 模式（牛客、卡码网）要求自己处理输入输出。Java 推荐用 BufferedReader 代替 Scanner（数据量大时 Scanner 慢一个数量级）：

输入格式示例：
4 4        ← n 个节点，m 条边
1 2 5      ← 起点 终点 边权
1 3 3
3 4 2
2 4 7

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());   // 节点数
        int m = Integer.parseInt(st.nextToken());   // 边数
 
        // 方式一：邻接表（无向图每条边存两遍）
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        // 方式二：邻接矩阵（带权图），grid[u][v] = w
        int[][] grid = new int[n + 1][n + 1];
 
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());   // 无权图可省
            graph.get(u).add(v);
            graph.get(v).add(u);        // 有向图删掉这一行
            grid[u][v] = w;
        }
        // ... 后续算法
    }
}

两个细节：节点编号若从 1 开始，数组开 n+1 避免下标偏移；StringTokenizer 比 split(" ") 更快更省内存。

三、DFS / BFS 遍历框架

无论什么图论题，遍历框架都是这副骨架，区别只在"访问节点时做什么"：

// visited 数组：防止成环图里绕圈死循环，树和网格类题目同样需要
boolean[] visited = new boolean[n + 1];
 
// DFS：递归深入，一条路走到黑再回头
private void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
    visited[node] = true;                      // 进入即标记
    for (int next : graph.get(node)) {
        if (!visited[next]) {
            dfs(graph, next, visited);
        }
    }
}
 
// BFS：队列逐层扩散，适合求无权图最短步数
private void bfs(List<List<Integer>> graph, int start, boolean[] visited) {
    Deque<Integer> queue = new ArrayDeque<>();
    queue.offer(start);
    visited[start] = true;                     // 入队时标记，防止重复入队
    while (!queue.isEmpty()) {
        int cur = queue.poll();
        for (int next : graph.get(cur)) {
            if (!visited[next]) {
                visited[next] = true;          // 关键：入队瞬间就标记
                queue.offer(next);
            }
        }
    }
}

防环三原则：DFS 进入节点立刻标记；BFS 在入队时标记（不是出队时，否则同一节点会被塞进队列多次，复杂度爆炸）；连通块计数时每发现一个未访问节点就启动一次搜索并统计。

四、专题地图

本专题后续文章按依赖关系排列：

岛屿系列（网格 DFS/BFS）：四连通遍历的十几种变体，训练"在矩阵上跑图论"的手感。
并查集：动态连通性查询，两个节点的连通关系能合并、能查询，省掉重复遍历。
最小生成树（Prim / Kruskal）：n 个节点连成一棵树使总边权最小，Kruskal 恰好建立在并查集之上。
拓扑排序：有向无环图的线性排序，解决"先后依赖"问题（课程表是它的标准脸）。
最短路：Dijkstra（单源、无负权）、Bellman-Ford（能处理负权）、Floyd（多源），选型口诀见第 7 篇。

学习顺序就按 1→5，岛屿是手 Warmup，并查集和拓扑各是一个固定模板，最短路的算法选择最烧脑放在最后。

五、LeetCode 题单总表

DFS / BFS 与岛屿

题号	题名	一句话考点
200	岛屿数量	淹岛法：访问过的 1 改成 0
695	岛屿的最大面积	遍历同时统计连通块大小
463	岛屿的周长	数格子边界而非遍历
130	被围绕的区域	从边界反向 DFS 淘汰不死区
417	太平洋大西洋水流	从海洋倒着往高处走
827	最大人工岛	岛屿编号 + 空格处合并统计

并查集

题号	题名	一句话考点
547	省份数量	连通块个数即并查集根的个数
684	冗余连接	加边时两端已同根，这条边就是答案
685	冗余连接 II	有向树需分情况讨论入度
1971	寻找图中是否存在路径	并查集判连通的最直接应用

拓扑排序

题号	题名	一句话考点
207	课程表	Kahn 判环：出队数是否等于 n
210	课程表 II	记录出队顺序即为拓扑序

最短路

题号	题名	一句话考点
743	网络延迟时间	Dijkstra 求单源最短路的标准题
1631	最小体力消耗路径	二分/BFS/Dijkstra 多解法对比
1334	阈值距离内邻居最少的城市	n 次 Dijkstra 或 Floyd

六、学习建议

建图和读入模板先抄熟，ACM 模式的输入解析不值得每次重新发明。
每种算法先在纸上走一遍小例子（Dijkstra 手动更新 dist 数组、并查集手动合并），再写代码。
同一道题尽量用两种方法做：岛屿数量用 DFS 写一遍再用 BFS 写一遍，冗余连接用并查集体会它比 DFS 省在哪。
最短路部分按"有无负权 → 单源还是多源"两问选算法，别上来就背代码。

下一篇从并查集开始——它是图论专题里性价比最高的模板，二十行代码解决一类问题。

参考

代码随想录 · 图论专题