1.图
何谓图？
图是描述世间万物关系的一种方式
节点+边隐式图
状态（结点）不确定（明显）
关系（边）不确定（明显）
如何确定状态和关系（重点）
2.图搜索
按某种顺序访问“图”中所有的节点
顺序
深度优先（优先往深处走）
广度优先（优先走最近的）时间复杂度 O(n + m)
空间复杂度？
给出图G，要求求从入口v1访问到每一个点
两种遍历方式的数据结构
栈（递归，深度优先）
队列（广度优先）广度优先找出的路径，经过节点数最少
深度优先伪代码
void DFS(int v)
visited[v] = true
for (v的每一个邻接点w)
if (!visited[w])//如果没有被访问过
DFS(w)
- 广度优先伪代码：
void BFS(int x)
visited[x] = true
Q.push(x)
While (!Q.empty())
v = Q.pop()
for (v的每个邻接点w)
if (!visited[w])
visited[w] = true
Q.push(w)
3.隐式图搜索
3.1 N皇后问题
在N*N的棋盘上摆放N个皇后，使得任意两个皇后都不能处于同一行、同一列或同一斜线上
回溯法（暴力搜索万金油）
本质：深度优先（隐式图搜索）
如何定义状态，关系？
时间复杂度 O(NN)（状态空间）
剪枝（确定性）
作业题：你写的代码能跑多少个皇后？
Leetcode 51
3.2 骑士游历问题
- 国际象棋棋盘上，有一个骑士（马）从左下角出发，是否能不重复的遍历每一个格子
- 没啥好的办法，考虑暴力
- 如何定义状态，关系？
- 除了剪枝，还有什么办法？（求任意解和所有解）
- 启发式(A*)
改变搜索顺序
不确定性
3.3 种子填充法
- Flood Fill洪水填充法
- 目标：标记某块封闭的区域，并找出其边界 .如何定义状态，关系？
- BFS犹如墨汁滴入清水
- Leetcode 200. Number of Islands
- Leetcode 130. Surrounded Regions
3.4 八数码
3*3的方格内有编号1-8的方块，求最少的步数，恢复这些方块的顺序
深度优先 or广度优先？
判重（Hash）
双向搜索
起始点和目标点，轮流扩展
Hash表判断相遇
复杂度启发式
价值函数（启发函数）
优先队列（堆）
3.5 迭代加深
- 求最优 ->求判定
- 不需要判重
- 搜到即是最优
- 前一个阶段相对下一个阶段仅仅是常数
- 迭代加深 +启发式（IDA*）
4.总结
DFS vs BFS
都为暴力搜索，但搜索顺序不同
栈 vs队列
可行解 vs最优解
递归 vs非递归
空间占用，BFS需要存储状态，DFS无需事无绝对，仅供参考
参考
- 1）面试求职 第四期
