Shortest Path
Shortest Path
BFS 最短路
无权图
01图，每条边的权值为0或1
状态转换问题
状态转换问题的最短步骤数。图的节点表示状态，边表示状态之间的合法转换。每次转换可以视为一步，无需考虑权值。
示例问题：
- 八数码问题（求解从初始状态到目标状态的最少移动次数）。
- 字梯问题（从一个单词转换到另一个单词，每次只能变更一个字母）。
方法： 将状态看作图的节点，合法的状态转换看作边，用 BFS 搜索状态空间。
哈希表，图中存在环，同一个节点可能重复进入队列，为了避免重复入队，在入队前标记 visited
Java: HashMap / HashSet
Java 队列建议 new ArrayDeque (链表比数组慢)
无权图
Word Ladder
简单图最短路径
给出两个单词(start和end)和一个字典，找出从start到end的最短转换序列，输出最短序列的长度。
Knight Shortest Path
简单图最短路径，八个方向坐标变换
飞行棋I
从数组的最左侧跳到最右侧，只能向右跳，一步跳 1-6 格，有一些格子之间直接飞过去不耗费步数，问最少跳几步
只能向右跳->方向性 ->DP
如果没有这个信息的话，就不能DP但是可以用BFS+
问最少步数，可能是哪些算法?
A. BFS (高概率)
B. DP (次高概率)
C. DFS (几乎没有，最短路上复杂度太大不优)
D. Shortest Path Algorithm (标准最短路面试一般不考)
距离之和最短
矩阵 vs 图
图 Graph
N个点，M条边，M最大是 O(N^2) 的级别，图上BFS时间复杂度 = O(N + M)
- 说是O(M)问题也不大，因为M一般都比N大
所以最坏情况可能是 O(N^2)
矩阵 Matrix
R行C列，RC个点，RC*2 条边(每个点上下左右4条边，每条边被2个点共享)。 矩阵中BFS时间复杂度 = O(R * C)
矩阵根据题意可以是简单图也可以是复杂图，一般情况下是简单图一步一步走，那个球滚动到边界的题就是一个复杂图，每次滚动的距离不一定，且是一个隐式图
图上的例题
- 判断一个图是否是一棵树
- 搜索图中最近值为target的点
- 无向图连通块
矩阵上的例题
- 僵尸多少天吃掉所有人
- 建邮局问题 Build Post Office II
隐式图 Implicit Graph
隐式图：隐式图是仅给出初始结点、目标结点以及生成子结点的约束条件（题意隐含给出），要求按扩展规则应用于扩展结点的过程，找出其他结点，使得隐式图的足够大的一部分编程显式，直到包含目标结点为止。
抽象问题，没有明确告诉什么是点，什么是边：
状态是点、二元关系是边
矩阵是一个非常典型的隐式图，每次都按照拓展规则去找下一个访问的结点
单词接龙也是一个典型的隐式图
隐式图是仅给出初始结点、目标结点以及生成子结点的约束条件（题意隐含给出），要求按扩展规则应用于扩展结点的过程，找出其他结点，使得隐式图的足够大的一部分编程显式，直到包含目标结点为止。
推多米诺