02.4.2.1 图表示与 DFS/BFS
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.2 图论与并查集
02.4.2.1-001 图是什么结构?
一句话结论
图由顶点集合 V 与边集合 E 组成,边可表示顶点间关系;分有向/无向、加权/无权;树是无环连通的特殊图。
概念解释
- 顶点:节点。
- 边:关系,可带权。
- 有向:边有方向;无向:双向等价。
原理流程
- 确定顶点编号。
- 按边建关系。
- 遍历或计算。
代码 / 图示
无向:A — B
有向:A → B
加权:A —(3)→ B
常见误区
- 误区:图就是树;正解:图可有环与不连通。
- 误区:边只能存邻接关系;正解:可带权值。
追问
- Q:度是什么? A:无向图关联边数;有向分入度出度。
- Q:连通图定义? A:任意两顶点间有路径。
02.4.2.1-002 邻接表怎么表示图?
一句话结论
每个顶点挂一个链表/列表存其邻接点;空间 O(V+E),适合稀疏图;建图时逐条边把目标加入对应链表。
概念解释
- 表数组:顶点下标。
- 链表:邻接点。
- 稀疏省空间。
原理流程
- 初始化 V 个空列表。
- 遍历边集加入邻接表。
- 有向只加一侧,无向加两侧。
代码 / 示例
List<Integer>[] g = new List[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] e : edges) {
g[e[0]].add(e[1]);
g[e[1]].add(e[0]); // 无向图
}
常见误区
- 误区:无向图只加一侧;正解:两侧都要挂。
- 误区:重边未处理;正解:按题意允许重复或去重。
追问
- Q:加权图邻接表存什么? A:存邻接点 + 权值的二元组。
- Q:邻接表遍历邻接点代价? A:该顶点度次。
02.4.2.1-003 邻接矩阵怎么表示图?
一句话结论
g[i][j] 存边是否存在(或权值);空间 O(V²),判断两点是否相邻 O(1),适合稠密图;稀疏图浪费空间。
概念解释
- 二维数组。
- 位置对应边。
- 稠密高效。
原理流程
- 建 V×V 矩阵。
- 边置 1/权值。
- 邻接查询查矩阵。
代码 / 示例
int[][] g = new int[n][n];
for (int[] e : edges) g[e[0]][e[1]] = 1;
常见误区
- 误区:稀疏图用矩阵;正解:稀疏用邻接表省空间。
- 误区:矩阵遍历所有邻接点 O(度);正解:需扫整行 O(V)。
追问
- Q:无权图矩阵存什么? A:0/1,无边用 0 或约定大数。
- Q:自环怎么记? A:对角元素。
02.4.2.1-004 邻接表与邻接矩阵怎么选?
一句话结论
稀疏图(E 远小于 V²)选邻接表,空间 O(V+E);稠密图、频繁判断两点相邻选矩阵,查询 O(1);按边密度与操作类型选型。
概念解释
- 密度:E/V²。
- 操作:遍历邻接 vs 判相邻。
- 空间权衡。
原理流程
- 估算边密度。
- 看主要操作。
- 选表示。
代码 / 图示
稀疏:邻接表 O(V+E)
稠密:邻接矩阵 O(V²)
常见误区
- 误区:邻接表判相邻 O(1);正解:需遍历链表。
- 误区:矩阵遍历邻接点快;正解:扫行 O(V)。
追问
- Q:网格图用什么表示? A:二维数组本身即矩阵,坐标直接邻居。
- Q:链表邻接 vs 数组邻接表? A:数组扩容方便,常见 ArrayList。
02.4.2.1-005 图的 DFS 递归怎么做?
一句话结论
从起点递归访问未访问邻接点,访问即标记;沿一条路径走到尽头再回溯;O(V+E) 时间 O(V) 访问标记 + O(h) 递归栈。
概念解释
- 深度优先:一条路走到底。
- visited 防重复。
- 递归回溯。
原理流程
- 起点标记访问。
- 遍历邻接点,未访问则递归。
- 回溯后继续其余邻接。
代码 / 示例
void dfs(int u, List<Integer>[] g, boolean[] vis) {
vis[u] = true;
for (int v : g[u]) {
if (!vis[v]) dfs(v, g, vis);
}
}
常见误区
- 误区:访问后不标记导致重复递归;正解:进入即标记。
- 误区:递归深度过大爆栈;正解:深图改迭代 DFS。
追问
- Q:DFS 能求最短路径吗? A:无权图不保证,BFS 才行。
- Q:递归栈深最坏? A:O(V)。
02.4.2.1-006 图的 DFS 迭代怎么做?
一句话结论
显式栈存待访问节点;弹出后标记,邻接未访问节点压栈;与递归等价,避免调用栈溢出;注意入栈即标记防重复入栈。
概念解释
- 显式栈模拟递归。
- 标记时机。
- 邻接压栈。
原理流程
- 起点入栈标记。
- 弹出处理。
- 未访问邻接压栈标记。
代码 / 示例
Deque<Integer> st = new ArrayDeque<>();
st.push(start);
vis[start] = true;
while (!st.isEmpty()) {
int u = st.pop();
for (int v : g[u]) {
if (!vis[v]) { vis[v] = true; st.push(v); }
}
}
常见误区
- 误区:弹出时才标记;正解:入栈即标记,避免重复入栈。
- 误区:栈 DFS 顺序与递归完全一致;正解:邻接压栈顺序影响结果。
追问
- Q:迭代 DFS 栈空间? A:O(V)。
- Q:需要记录路径? A:栈中保存节点链或父节点。
02.4.2.1-007 图的 BFS 怎么做?
一句话结论
队列逐层扩展:起点入队标记,弹出后邻接未访问节点入队;无权图按距离分层,首次到达即最短;O(V+E) 时间 O(V) 队列。
概念解释
- 广度优先:按距离展开。
- FIFO 保层序。
- 首达最短。
原理流程
- 起点入队标记。
- 弹出扩展邻接。
- 未访问入队标记。
代码 / 示例
Queue<Integer> q = new ArrayDeque<>();
q.offer(start);
vis[start] = true;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : g[u]) {
if (!vis[v]) { vis[v] = true; q.offer(v); }
}
}
常见误区
- 误区:BFS 用栈;正解:队列保层序。
- 误区:出队才标记;正解:入队即标记防重复。
追问
- Q:BFS 求最短步数? A:记录层号或父节点回溯。
- Q:多源 BFS? A:所有源同时入队。
02.4.2.1-008 visited 标记为什么要在入队/入栈时做?
一句话结论
若弹出时才标记,同一节点可能被多个邻接点重复入队/入栈,队列膨胀甚至错误;入结构即标记保证每节点只进一次。
概念解释
- 重复入队:多邻接指向同一节点。
- 标记时机。
- 每节点一次。
原理流程
- 发现未访问节点。
- 立即置 visited。
- 再入结构。
代码 / 图示
入队前:vis[v]=true; q.offer(v)
常见误区
- 误区:弹出后再标 visited;正解:入结构前标记。
- 误区:标记集合用节点值;正解:按编号/引用判重。
追问
- Q:需要允许重复访问吗? A:普通遍历不需要;状态扩展图另论。
- Q:标记空间? A:O(V) 布尔数组或哈希。
02.4.2.1-009 怎么统计连通分量?
一句话结论
遍历所有顶点,未访问则开启一次 DFS/BFS 把该分量全部标记,分量计数加一;O(V+E) 时间 O(V) 标记空间。
概念解释
- 分量:内部连通、与外部不连通。
- 外层枚举起点。
- 内层遍历整分量。
原理流程
- 遍历每个顶点。
- 未访问则计数并遍历。
- 访问过跳过。
代码 / 示例
int count = 0;
for (int i = 0; i < n; i++) {
if (!vis[i]) { count++; dfs(i, g, vis); }
}
常见误区
- 误区:只从固定起点遍历;正解:外层枚举所有顶点覆盖不连通图。
- 误区:分量计数在递归内加;正解:每次新起点加一。
追问
- Q:并查集求分量? A:合并后统计根节点数,见 02.4.2.3。
- Q:网格图连通分量? A:坐标作顶点,四方向邻居。
02.4.2.1-010 岛屿数量(LC 200)怎么做?
一句话结论
网格作无向图,遍历每个陆地格子;未访问陆地触发 DFS/BFS 把整座岛淹没/标记,分量数即岛屿数;O(mn) 时间 O(mn) 最坏栈/队列。
概念解释
- 顶点:格子。
- 边:上下左右。
- 分量:岛屿。
原理流程
- 扫描网格。
- 遇未访问陆地计数并遍历淹没。
- 水与已访问跳过。
代码 / 示例
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length, count = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == '1') { count++; dfs(grid, i, j); }
return count;
}
private void dfs(char[][] g, int i, int j) {
if (i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] == '0') return;
g[i][j] = '0';
dfs(g, i + 1, j); dfs(g, i - 1, j);
dfs(g, i, j + 1); dfs(g, i, j - 1);
}
常见误区
- 误区:越界判断遗漏;正解:四个方向先判边界。
- 误区:未标记导致重复淹没;正解:访问即改水。
追问
- Q:BFS 版本? A:队列存坐标,逐层扩散。
- Q:并查集版本? A:陆地相邻合并,统计集合数。
02.4.2.1-011 克隆图(LC 133)怎么做?
一句话结论
哈希表存原节点 → 克隆节点;DFS/BFS 遍历原图,首次访问建克隆并复制邻接关系;避免环导致重复克隆;O(V+E) 时间 O(V) 哈希。
概念解释
- 克隆:值与邻接复制。
- 映射:原图到副本。
- 环保护。
原理流程
- 原节点查映射,无则建副本。
- 遍历邻接递归克隆。
- 邻接表接副本。
代码 / 示例
private Map<Node, Node> map = new HashMap<>();
public Node cloneGraph(Node node) {
if (node == null) return null;
if (map.containsKey(node)) return map.get(node);
Node copy = new Node(node.val);
map.put(node, copy);
for (Node next : node.neighbors) copy.neighbors.add(cloneGraph(next));
return copy;
}
常见误区
- 误区:不存映射导致环上重复克隆;正解:先登记副本再递归。
- 误区:邻接表接原节点;正解:接克隆副本。
追问
- Q:BFS 克隆? A:队列遍历,出队补邻接副本。
- Q:图有环会栈溢出吗? A:映射防重复,递归深度仍受环长影响。
02.4.2.1-012 判断二分图(LC 785)怎么做?
一句话结论
染色法:未染色起点染 0,邻接点染相反色;邻接点同色则非二分图;BFS/DFS 均可;O(V+E) 时间 O(V) 颜色数组。
概念解释
- 二分图:顶点分两组,边跨组。
- 染色:两色交替。
- 冲突判定。
原理流程
- 枚举未染色顶点。
- 染色并遍历邻接。
- 邻接同色返回 false。
代码 / 示例
public boolean isBipartite(int[][] g) {
int n = g.length;
int[] color = new int[n]; // 0 未染, 1/-1
for (int i = 0; i < n; i++) {
if (color[i] != 0) continue;
Queue<Integer> q = new ArrayDeque<>();
q.offer(i); color[i] = 1;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : g[u]) {
if (color[v] == 0) { color[v] = -color[u]; q.offer(v); }
else if (color[v] == color[u]) return false;
}
}
}
return true;
}
常见误区
- 误区:只检查单连通分量;正解:外层枚举所有顶点。
- 误区:无向图邻接重复染色;正解:已染邻接只校验冲突。
追问
- Q:奇环与二分图关系? A:含奇环必非二分图。
- Q:网格黑白染色? A:坐标奇偶分组即二分。
02.4.2.1-013 图中环怎么检测?
一句话结论
有向图 DFS 三色标记:访问中(栈内)遇访问中节点即有环;无向图需记录父节点,避免把回边当环;拓扑排序结果不足 V 也说明有环。
概念解释
- 有向:递归栈内节点。
- 无向:父节点排除。
- 拓扑: Kahn 残留入度。
原理流程
- 白未访问、灰在栈、黑已完成。
- 遇灰节点判环。
- 完成置黑。
代码 / 示例
// 有向:0 未访 1 访问中 2 完成
boolean dfs(int u) {
state[u] = 1;
for (int v : g[u]) {
if (state[v] == 1) return true;
if (state[v] == 0 && dfs(v)) return true;
}
state[u] = 2;
return false;
}
常见误区
- 误区:无向图不记父节点把回边判环;正解:父节点跳过。
- 误区:有向图用 visited 布尔即可;正解:需区分在栈与已完成。
追问
- Q:环上节点怎么找? A:记录栈路径。
- Q:拓扑排序判环? A:入队处理数 < V 即有环。
02.4.2.1-014 网格图遍历和普通图有什么对应关系?
一句话结论
格子是顶点,上下左右是边;坐标编码为一维下标即可套邻接表算法;边界判断代替邻接表越界;DFS/BFS/并查集框架通用。
概念解释
- 坐标 → 顶点编号。
- 方向数组。
- 边界即无边。
原理流程
- 方向数组四方向。
- 越界/非目标跳过。
- 复用图遍历框架。
代码 / 示例
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
常见误区
- 误区:网格题单独写一套逻辑;正解:抽象成图遍历。
- 误区:方向遗漏斜向;正解:按题意四/八方向。
追问
- Q:八方向岛屿? A:方向数组加四斜向。
- Q:网格 visited 怎么存? A:二维布尔或原地改值。
02.4.2.1-015 腐烂橘子(LC 994)多源 BFS 怎么做?
一句话结论
所有腐烂橘子同时入队作为第 0 层,BFS 逐层扩散新鲜橘子;记录轮数与剩余新鲜数;O(mn) 时间 O(mn) 队列。
概念解释
- 多源:起点集合。
- 层序扩散。
- 未感染判定。
原理流程
- 统计新鲜数,腐烂橘子入队。
- 逐层扩散,新鲜变腐计入层。
- 仍有新鲜返回 -1,否则返回轮数。
代码 / 示例
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length, fresh = 0, rounds = 0;
Queue<int[]> q = new ArrayDeque<>();
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) q.offer(new int[]{i, j});
else if (grid[i][j] == 1) fresh++;
}
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty() && fresh > 0) {
int size = q.size(); rounds++;
for (int i = 0; i < size; i++) {
int[] c = q.poll();
for (int[] d : dirs) {
int x = c[0]+d[0], y = c[1]+d[1];
if (x>=0&&y>=0&&x<m&&y<n&&grid[x][y]==1) {
grid[x][y]=2; fresh--; q.offer(new int[]{x,y});
}
}
}
}
return fresh == 0 ? rounds : -1;
}
常见误区
- 误区:单个腐烂橘子 BFS;正解:多源同时入队。
- 误区:轮数按节点数计;正解:按层计。
追问
- Q:为什么不用 DFS? A:同时扩散的最短时间需 BFS 层序。
- Q:初始无新鲜橘子? A:轮数 0。
02.4.2.1-016 DFS 与 BFS 怎么选型?
一句话结论
需要全路径/回溯/环检测用 DFS;无权最短路径、层序扩散、多源感染用 BFS;空间两者最坏 O(V),DFS 栈深受树形影响,BFS 队列受层宽影响。
概念解释
- DFS:深度优先,路径型。
- BFS:广度优先,距离型。
- 结构与目标匹配。
原理流程
- 看是否求最短距离。
- 看是否需要回溯路径。
- 选遍历方式。
代码 / 图示
路径/拓扑/环:DFS
最短路/层序:BFS
常见误区
- 误区:DFS 也能求无权最短路;正解:DFS 不保证首达最短。
- 误区:BFS 栈实现;正解:队列。
追问
- Q:空间谁更省? A:链状 BFS 省,宽层 DFS 省,按形状。
- Q:递归 DFS 爆栈? A:改迭代 DFS。
02.4.2.1-017 邻接表建图有哪些细节?
一句话结论
顶点编号从 0 连续;有向边只加目标侧,无向加两侧;加权边存二元组;重复边与自环按题意处理;入度在加边时同步统计。
概念解释
- 编号口径。
- 方向。
- 权值存储。
原理流程
- 初始化邻接表。
- 逐条边挂接。
- 统计入度等辅助量。
代码 / 图示
有向:g[u].add(v)
无向:g[u].add(v); g[v].add(u)
加权:g[u].add(new int[]{v, w})
常见误区
- 误区:有向图误加两侧;正解:按方向。
- 误区:编号不连续硬开数组;正解:离散化或哈希映射。
追问
- Q:边集数组怎么存? A:列表存边元组,按需建表。
- Q:动态加边? A:邻接表尾插即可。
02.4.2.1-018 图遍历有哪些边界用例?
一句话结论
空图、单顶点、无边、自环、重边、不连通多分量、有向不对称、网格全水/全陆;判空、外层枚举与方向边界。
概念解释
- 空与最短。
- 不连通。
- 特殊边。
原理流程
- 空图返回默认。
- 外层枚举顶点。
- 特殊边按口径处理。
代码 / 图示
V=0 / 单点 / 孤立点
自环 / 重边
多分量
常见误区
- 误区:默认图连通;正解:外层枚举覆盖分量。
- 误区:自环重复访问;正解:visited 拦截。
追问
- Q:无边图 BFS? A:只处理起点,队列为空结束。
- Q:网格空行空列? A:先判维度。
02.4.2.1-019 图遍历复杂度怎么算?
一句话结论
DFS/BFS 均 O(V+E) 时间:每顶点访问一次,每条边检查常数次;访问标记 O(V),递归栈或队列最坏 O(V);网格图 V=mn、E=O(mn)。
概念解释
- 顶点一次。
- 边常数次。
- 辅助结构按规模。
原理流程
- 统计顶点与边。
- 每邻接边遍历一次。
- 标注栈/队列规模。
代码 / 图示
邻接表:O(V+E) 时间 / O(V) 空间
矩阵:遍历邻接 O(V²)
常见误区
- 误区:图遍历 O(V²) 恒成立;正解:邻接表 O(V+E)。
- 误区:递归栈不计空间;正解:O(h) ≤ O(V)。
追问
- Q:邻接矩阵遍历全图? A:O(V²) 扫行。
- Q:BFS 队列最坏规模? A:O(V),宽层时接近 V。
02.4.2.1-020 图遍历常见变体考点有哪些?
一句话结论
连通分量、岛屿、克隆图、二分图、环检测、多源 BFS 扩散、网格最短路径;主线是 visited 标记 + DFS/BFS 框架,按目标补距离/颜色/映射。
概念解释
- 框架:遍历 + 标记。
- 附加:距离/颜色/克隆映射。
- 场景变体。
原理流程
- 套用 DFS/BFS 框架。
- 按题维护附加状态。
- 边界与多分量检查。
代码 / 图示
分量:计数
距离:层号
染色:颜色数组
克隆:原图映射
常见误区
- 误区:变体题重写遍历逻辑;正解:框架复用,附加状态独立。
- 误区:多源问题只放一个起点;正解:全部源同时入队。
追问
- Q:无权最短路径 BFS 怎么回溯路径? A:记录父节点。
- Q:图 DFS 后序用途? A:拓扑排序与强连通分量。