信息技术大学
图基础
数据结构与算法·面试高频 · 第 2 章 树与图
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
图基础
数据结构与算法·面试高频 · 第 2 章 树与图
邻接表与邻接矩阵
两种存图姿势：矩阵查边 O(1) 费空间，邻接表省空间按点扫邻居。
邻接矩阵
n×n 矩阵，查边 O(1)，空间 O(n²)
邻接表
每点挂邻居链，空间 O(n+m)，稀疏图首选
选型
稠密图或频繁查边用矩阵，遍历为主用表
DFS/BFS 遍历
DFS 一条道走到黑靠栈，BFS 层层推进靠队列：两套模板吃遍图论基础。
DFS
递归或显式栈，深入到底再回溯
BFS
队列逐层扩展，无权图最短路即它
防回头
visited 集合记录足迹，有环图必备
拓扑排序与课程表
有向无环图排课表：入度清零就出列，出不完说明有环。
Kahn 算法
入度 0 进队列，出列时把邻居入度减一
判环
出列数少于节点数即有环，无合法排序
DFS 法
后序序列反转即拓扑序，三色标记判环
岛屿问题系列
网格即图：每个陆地格是节点，四向是边；沉岛 DFS/BFS 一招通吃。
网格建模
格子坐标即节点，上下左右即邻接关系
沉岛
访问过的陆地改字符标记，省掉 visited 集合
全家桶
数量、最大面积、封闭岛屿、飞地同一套路
本节要点
- ✓稀疏用邻接表，频繁查边用矩阵
- ✓DFS 深栈，BFS 层队，visited 防环
- ✓拓扑排序：入度清零出列，出不完有环
- ✓岛屿：网格建模，沉岛标记
延伸主题：刷课程表 I/II写一遍岛屿最大面积
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1无权图最短路为什么是 BFS 而不是 DFS？
参考答案BFS 按层扩展，第一次到达某点时经过的边数必然最少；DFS 深入可能绕远，先到不代表最短。边权不一才轮到 Dijkstra 上场。
2拓扑排序为什么只对 DAG 有意义？
参考答案环内节点互相依赖，入度永不清零，排不出合法顺序。拓扑序本质是把偏序关系线性化，环意味着自相矛盾的约束，天然无解。
3岛屿问题的「沉岛」为什么可行？
参考答案把访问过的陆地字符改成非陆标记，等价于 visited 集合，省掉 O(n²) 额外空间；不允许修改输入时，传入 visited 数组同理，套路不变。