1图是什么
说出三个生活中的图。
算法进阶 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2点、边、度
三角形的每个顶点度数是几？
3有向与无向
单行道地图属于哪种？
4带权图
地图上的边权通常表示什么？
5邻接矩阵
一千个点要多少格？
6邻接表
十万个点二十万条边，用哪种？
7链式前向星
这样存的好处是什么？
8图的深搜
不标记会怎样？
9图的广搜
边权不全为 1 还能用广搜求最短吗？
10连通分量
一次搜索走遍所有点说明什么？
第 1 页 · 背面（答案）
参考答案（家长）：2。
参考答案（家长）：如地铁线路、社交关系、赛程对阵表。
参考答案（家长）：两地之间的距离或耗时。
参考答案（家长）：有向图。
参考答案（家长）：邻接表，矩阵要一百亿格根本开不下。
参考答案（家长）：一百万格，还能接受。
参考答案（家长）：会绕圈子出不来，无限递归。
参考答案（家长）：全用数组，速度快、不用动态分配。
参考答案（家长）：整张图是连通的。
参考答案（家长）：不能，要用专门的最短路算法。
第 2 页 · 正面（题目）
11判断二分图
出现什么情况说明不是二分图？
12拓扑排序是什么
举一个有依赖关系的例子。
13拓扑排序怎么做
如果中途没有入度为 0 的点了，说明什么？
14拓扑排序判环
怎么知道"排不完"？
15最短路问题分类
求全班两两之间的距离，属于哪类？
16松弛操作
用一句话说清松弛。
17Dijkstra 的思想
为什么挑最小的那个可以直接确定？
18Dijkstra 的实现
为什么会有过期记录？
19Dijkstra 不能有负权
有负权该用什么？
20Bellman-Ford
第 n 轮还能松弛说明什么？
第 2 页 · 背面（答案）
参考答案（家长）：如课程先修、施工工序。
参考答案（家长）：染色时发现相邻两点已经同色。
参考答案（家长）：最后取出的点数少于总点数。
参考答案（家长）：图里有环，无法排出顺序。
参考答案（家长）：发现更短的路就更新记录。
参考答案（家长）：多源最短路。
参考答案（家长）：同一个点可能被多次更新入队，只有最新的有效。
参考答案（家长）：边权非负时，不可能再通过别人绕出更短的路。
参考答案（家长）：图里有负权环，最短路不存在。
参考答案（家长）：Bellman-Ford 或它的队列优化版。
第 3 页 · 正面（题目）
21队列优化的 Bellman-Ford
这个优化的直觉是什么？
22Floyd 算法
为什么 k 必须在最外层？
23Floyd 的适用范围
n 是 200，Floyd 要多少次运算？
24边权全为 1 用广搜
迷宫最少步数该用什么？
25记录路径
倒推出来的路径是什么顺序？
26最短路练习一
动手写完整。
27最短路练习二
这题该用哪个算法？
28分层图的思想
为什么要分层？
29最小生成树是什么
为什么恰好 n-1 条边？
30并查集
怎么判断两点是否已经连通？
第 3 页 · 背面（答案）
参考答案（家长）：要保证"用前 k 个点做中转"的状态被逐步完整扩展。
参考答案（家长）：没变化的点再去松弛也不会有新结果。
参考答案（家长）：广搜。
参考答案（家长）：八百万次，很快。
参考答案（家长）：Dijkstra 加前驱数组记录路径。
参考答案（家长）：从终点到起点，要反转一下。
参考答案（家长）：状态里多了"用了几次机会"，要把它放进图里表示。
参考答案（家长）：广搜，配上方向数组。
参考答案（家长）：看它们的祖先是不是同一个。
参考答案（家长）：少了不连通，多了会成环，这正是树的定义。