图的遍历¶
广度优先搜索¶
类似二叉树中的层序遍历。
算法思想¶
从任意一个顶点开始访问，按照距离起始顶点的远近，逐层访问所有顶点。即先访问所有与起始顶点直接相邻的顶点（第一层），再访问与第一层顶点相邻且未访问的顶点（第二层），以此类推，直到所有顶点都被访问。
性能分析¶
求解单源最短路径问题¶
广度优先生成树¶
深度优先搜索¶
深度优先搜索 (Depth-First Search, DFS) 类似二叉树的先序遍历: 访问当前顶点后, 沿一条边尽量往深处走, 走不通再基于栈进行回溯, 换下一条边.
树没有环, 先序遍历不会重复碰到同一结点. 图可以有环, 必须另备 visited[], 每个顶点只访问一次, 否则会在环上打转.
算法思想¶
从任意顶点 \(v\) 出发:
-
访问 \(v\), 并标记为已访问
-
在 \(v\) 的邻接点里挑一个尚未访问的 \(w\), 对 \(w\) 递归做同样的事 (继续深入)
-
\(v\) 的邻接点全部访问过之后, 回溯到调用 \(v\) 的那个顶点, 换另一条未走完的边
-
若图不连通, 对每个尚未访问的顶点再调一次 DFS, 直到所有顶点都被访问
迷宫模型¶
想象一个迷宫模型, 走进死胡同就退回岔路口, 换另一条路, 这就是回溯(backtrack)的基本思想.
初学时可能会纠结迷宫应该怎么实现, 其实若规模不大, 只需一个二维数组, 用0表示通路, 1表示障碍:
int maze[MAX_ROW][MAX_COL] = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 1, 0},
};
用2来表示已经走过的格子:
void visit(int row, int col, struct point pre, int maze[MAX_ROW][MAX_COL],
struct point predecessor[MAX_ROW][MAX_COL])
{
struct point visit_point = { row, col };
maze[row][col] = 2;
predecessor[row][col] = pre;
push(visit_point);
}
上面的visit函数中:
-
pre表示当前格子的前一个格子 -
visit_point表示当前遍历到的格子 -
maze[row][col] = 2表示当前格子已经走过, 用2来覆盖 -
predecessor[row][col] = pre表示当前格子的前一个格子是pre, 用于辅助记录路径, 即每次遍历到某个格子时, 记录下它是从哪个格子走过来的. -
push(visit_point)表示将当前格子压栈, 便于后续的回溯:void push(struct point p) { stack[top++] = p; }思考我们需要回溯时的情况, 在DFS中, 只有在走不通时才需要回溯, 因此我们需要一个栈来记录路径, 记录的内容也很简单, 就是走过的格子. 这样, 栈中的序列就自底向上存储了从起点到当前格子的路径.
基于栈LIFO的特性, 我们每次回溯时, 只需要弹出栈顶元素, 返回值就是当前格子的前一个格子, 这样我们就可以回溯到前一个格子, 继续尝试其他方向:
struct point pop() { return stack[--top]; }后进先出逼着算法先把一条路走到底, 这才叫深度优先. 每个格子的前驱只有一个, 后继却可能有多个 (探索时往好几个方向都试过), 所以用前驱数组能从终点倒推回起点, 却不能只存一个后继来正向打印整条正确路线.
迭代实现¶
思考完遍历访问的方式以及路径存储与回溯的形式后, 我们就可以开始实现DFS的主逻辑了:
int dfs_traverse_base_iter(int maze[MAX_ROW][MAX_COL],
struct point predecessor[MAX_ROW][MAX_COL])
{
struct point p = { 0, 0 };
maze[p.row][p.col] = 2;
push(p);
while (!is_empty()) {
p = pop();
if (p.row == MAX_ROW - 1 /* goal */
&& p.col == MAX_COL - 1)
break;
if (p.col + 1 < MAX_COL /* right */
&& maze[p.row][p.col + 1] == 0)
visit(p.row, p.col + 1, p, maze, predecessor);
if (p.row + 1 < MAX_ROW /* down */
&& maze[p.row + 1][p.col] == 0)
visit(p.row + 1, p.col, p, maze, predecessor);
if (p.col - 1 >= 0 /* left */
&& maze[p.row][p.col - 1] == 0)
visit(p.row, p.col - 1, p, maze, predecessor);
if (p.row - 1 >= 0 /* up */
&& maze[p.row - 1][p.col] == 0)
visit(p.row - 1, p.col, p, maze, predecessor);
print_maze(maze);
sleep(1);
}
if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
printf("(%d, %d)\n", p.row, p.col);
while (predecessor[p.row][p.col].row != -1) {
p = predecessor[p.row][p.col];
printf("(%d, %d)\n", p.row, p.col);
}
} else {
return 0;
}
return 1;
}
抹去细节, 只保留主要逻辑就是这样:
/* 将起点标记为已走过并压栈; */
while (/*栈非空*/) {
/* 弹出栈顶格子 p; */
if (/* p 是终点 */) break;
/* 否则按右 / 下 / 左 / 上探索相邻格子; */
if (/* 相邻格可走且未走过 */)
/* 标记为已走过, 记下前驱为 p, 压栈; */
}
递归实现¶
既然我们用到了栈, 回顾递归调用的本质, 我们完全可以直接让系统帮我们维护一个栈, 这样我们就 可以避免显式使用栈带来的维护成本.
进入 dfs 相当于 push 当前格, return 相当于 pop / 回溯.
但是需要注意的是, 这并不是和迭代版字面上一一映射: 迭代一次循环可能把四个邻居都 push(这也是在执行时迭代版会出现遍历到路口时会先把路口的各个方向都先探出一格的原因1);
递归则是对一个邻居调用一次, 整段走完 (或已经找到) 才试下一个, 所以运气好的话会出现只走一条路就找到终点的情况:
Recursive implementation:
2 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 0 0 0 0
0 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 0 0 0
0 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 2 0 0
0 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 2 2 0
0 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 2 2 2
0 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 2 2 2
0 1 1 1 2
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 2 2 2
0 1 1 1 2
0 0 0 1 2
*********
Path found!
某一时刻还没返回的栈帧, 从底到顶就是起点到当前格. 这时前驱表 predecessor 不再需要了, 因为这时路径已经存储在调用堆栈上了:
| 迭代版 | 递归版 | |
|---|---|---|
| 栈里 | 待走的格子 (工作的显式栈, LIFO) | 当前这条路上还没返回的格子 |
| 路径在哪 | 不在栈上, 所以要 predecessor | 就在调用堆栈上 |
迭代循环里的三件事, 变成 dfs(row, col) 的三件事:
-
终止: 当前格是终点, 或四个方向都走不通
-
传递: 把格子标记成
2(相当于visited, 可以对比一下迭代实现中的visit函数, 结合上面阐述的递归的特性理解为什么只需要一行代码就能完成这一步) -
递归: 对每个在界内且仍是
0的邻居再调自己; 子调用返回1就立刻把1传回去, 也就不会再试别的方向了
int dfs(int row, int col, int maze[MAX_ROW][MAX_COL])
{
maze[row][col] = 2;
print_maze(maze);
sleep(1);
if (row == MAX_ROW - 1 && col == MAX_COL - 1)
return 1;
if (col + 1 < MAX_COL && maze[row][col + 1] == 0 && dfs(row, col + 1, maze))
return 1;
if (row + 1 < MAX_ROW && maze[row + 1][col] == 0 && dfs(row + 1, col, maze))
return 1;
if (col - 1 >= 0 && maze[row][col - 1] == 0 && dfs(row, col - 1, maze))
return 1;
if (row - 1 >= 0 && maze[row - 1][col] == 0 && dfs(row - 1, col, maze))
return 1;
return 0; /* 四边全死, 回溯 */
}
int dfs_traverse_base_recur(int maze[MAX_ROW][MAX_COL])
{
return dfs(0, 0, maze);
}
抹去细节:
int dfs(row, col)
{
/* 标记为已走过; */
if (/* 是终点 */) return 1;
/* 按右 / 下 / 左 / 上: 可走则 dfs(邻居); */
if (/* 子调用找到终点 */) return 1;
return 0;
}
上面走迷宫的DFS在找到终点就停, 主要是为了阐述DFS的基本思想; 下面图上的DFS则要访问所有顶点, 通了也还要继续.
基于图的DFS抽象¶
将迷宫模型抽象成到数据结构图, 把每个格子当成一个顶点, 上下左右可走的相邻格当成边, 我们就可以基于数据结构来实现DFS.
下面这张无向图从 \(1\) 出发, 邻接点按编号从小到大:
graph LR
A((1)) --- B((2))
A --- C((3))
B --- D((4))
B --- E((5))
C --- E使用DFS的一个查找路径如下:
visit 1, 邻接 2, 3
visit 2, 邻接 1(已访), 4, 5
visit 4, 邻接 2(已访) → 回溯
visit 5, 邻接 2(已访), 3
visit 3, 邻接 1(已访), 5(已访) → 回溯
序列: 1, 2, 4, 5, 3
若邻接表里 \(1\) 的边表是 \(3\) 再 \(2\), 序列就变成 \(1, 3, 5, 2, 4\). 两种都是合法 DFS, 邻接点次序不同, 遍历序列就不同.
递归实现¶
递归版把「当前路径」放在调用栈里, 回溯就是函数返回.
408中习惯用 FirstNeighbor / NextNeighbor 枚举邻接点.
bool visited[MAX_VERTEX_NUM];
void DFS(Graph G, int v) {
visit(v);
visited[v] = true;
for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
if (!visited[w])
DFS(G, w); // 树边 (v, w)
}
void DFSTraverse(Graph G) {
for (int i = 0; i < G.vexnum; ++i)
visited[i] = false;
for (int i = 0; i < G.vexnum; ++i)
if (!visited[i])
DFS(G, i); // 每个连通分量调一次
}
DFSTraverse 外层循环保证非连通图也能扫全. 无向图里调用 DFS 的次数等于连通分量个数.
递归本质是系统帮你维护一个栈. 显式栈也能写出 DFS, 栈顶是当前正在走的顶点, 还有未访问邻接点就压进去继续深入, 没有了就弹栈回溯, 正如上面的迷宫模型所示.
迭代实现¶
在数据结构的抽象下, DFS的迭代实现
性能分析¶
时间 = 访问 \(|V|\) 个顶点 + 检查每条边的邻接关系, 瓶颈在「找出邻接点」怎么存.
| 存储 | 找一个顶点的全部邻接点 | 整图 DFS |
|---|---|---|
| 邻接矩阵 | 扫一行 \(O(\|V\|)\) | \(O(\|V\|^2)\) |
| 邻接表 | 跟边走 \(O(\deg(v))\) | \(O(\|V\| + \|E\|)\) |
空间:
-
visited[]必占 \(O(|V|)\) -
递归栈 (或显式栈) 最坏 \(O(|V|)\): 图退化成一条链时, DFS 生成树高为 \(|V|-1\)
-
合计 \(O(|V|)\), 与 BFS 同阶 (BFS 的空间在队列上)
DFS 不保证最短路
无权图上从起点到终点, DFS 找到的只是「某条」路径. 同一迷宫用队列做广度优先, 才是边数最少的那条. 带权最短路见 Dijkstra / Floyd.
深度优先生成树和生成森林¶
DFS 中, 从 \(v\) 第一次走到尚未访问的 \(w\) 时, 边 \((v, w)\) 称为树边. 全部树边加上被访问的顶点, 构成一棵生成树.
上面的例子, 序列 \(1, 2, 4, 5, 3\) 对应树边 \(1{-}2\), \(2{-}4\), \(2{-}5\), \(5{-}3\):
1
|
2
/ \
4 5
\
3
剩下的边 \(1{-}3\) 连到祖先, 是回边, 说明图里有环. 连通无向图有 \(n\) 个顶点, 生成树恰好 \(n-1\) 条树边.
DFS 树往往又高又瘦 (一条路走到底); BFS 树往往又矮又宽 (按层铺开). 二者都是生成树, 但都不是最小生成树: MST 要边权之和最小, 和遍历次序无关.
邻接表不唯一时, 深度优先生成树也不唯一, 道理和遍历序列一样.
图不连通时, 对每个连通分量各长出一棵 DFS 树, 这些树合起来叫深度优先生成森林. 有向图里从某点出发未必能到所有顶点, 一次 DFS 只覆盖「从该点可达」的部分, 要从每个未访问顶点再出发, 同样得到森林.