Shortest Path

最短路

简单图：BFS

复杂图：Floyd, Dijkstra, Bellman-ford, SPFA

面试中一般不考复杂图最短路径问题（除了hard）

问最长路径

BFS 是否可以做? 应该用什么算法呢?

图可以分层：动态规划 Dynamic Programming

图不可分层：深度优先搜索 DFS

分层意思是：路径有一定方向性，不能绕圈（DAG），第i层的点只能走到第i+1层不能回到底 i-1 层

哈希表，图中存在环，同一个节点可能重复进入队列，为了避免重复入队，在入队前标记 visited

Java: HashMap / HashSet

Java 队列建议 new ArrayDeque (链表比数组慢)

简单图

Word Ladder

简单图最短路径

给出两个单词(start和end)和一个字典，找出从start到end的最短转换序列，输出最短序列的长度。

Knight Shortest Path

简单图最短路径，八个方向坐标变换

复杂图

用 Dijkstra 或者 SPFA

负数边问题：面试不考，且竞赛也很少考，主要是负环怎么解决？是否可以一直遍历

点不能重复走还是边不能重复走

点：哈密尔顿路

边：欧拉路

---

飞行棋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

隐式图：隐式图是仅给出初始结点、目标结点以及生成子结点的约束条件（题意隐含给出），要求按扩展规则应用于扩展结点的过程，找出其他结点，使得隐式图的足够大的一部分编程显式，直到包含目标结点为止。

抽象问题，没有明确告诉什么是点，什么是边：

状态是点、二元关系是边

矩阵是一个非常典型的隐式图，每次都按照拓展规则去找下一个访问的结点

单词接龙也是一个典型的隐式图

隐式图是仅给出初始结点、目标结点以及生成子结点的约束条件（题意隐含给出），要求按扩展规则应用于扩展结点的过程，找出其他结点，使得隐式图的足够大的一部分编程显式，直到包含目标结点为止。

推多米诺