深度优先搜索（DFS）算法

图的深度优先搜索（DFS）类似于树的先序遍历，尽可能“深”地搜索一个图。

DFS 算法

基本思想

首先访问某一起始顶点v，再由v出发，访问与v邻接且未访问过的顶点w，在以w为起始顶点出发，访问与w邻接且未访问过的顶点……

void DFS (Graph G, int v) { //从顶点v出发，深度优先遍历图G
    visit(v); //访问v
    visited[v] = true; //标记v已访问

    //依次对v的所有未访问过的邻接顶点深度优先遍历
    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) { //遍历邻接顶点
        if (!visited[w]) { //未访问过
            DFS(G, w);
        }
    }
}

以下图为例，采用深度优先搜索，且以字母顺序优先，遍历顺序如下：

$$\begin{aligned} a -> b -> c &-> e \\ -> d &-> f \\ &-> g \end{aligned}$$

graph LR
    a((a))
    b((b))
    c((c))
    d((d))
    e((e))
    f((f))
    g((g))

    a --- b & c
    b --- c & d
    c --- e
    d --- f & g

性能分析

• 空间复杂度

  DPS利用递归，需要一个以每个顶点为起点的DFS函数递归工作栈，空间复杂度为 $O(|V|)$

  （$|V|$ 表示顶点的个数）

• 时间复杂度

  遍历图实际上是对每一个顶点查找其邻接点的过程，时间复杂度取决于图的存储结构。

  • 邻接矩阵

    查找每个顶点的邻接点的时间为 $O(|V|)$，总时间复杂度 $O(|V^2|)$

  • 邻接表

    查找所有顶点的邻接点的时间为 $O(|E|)$，（即有多少条边，查找多少次邻接点），访问顶点所需时间为 $O(|V|)$，总时间复杂度 $O(|V|+|E|)$

DFS 例题

迷宫问题

描述

定义一个二维数组 N*M ，如 5 × 5 数组下所示：

$$maze[5][5] = \begin{pmatrix} 0, 1, 0, 0, 0,\\ 0, 1, 1, 1, 0,\\ 0, 0, 0, 0, 0,\\ 0, 1, 1, 1, 0,\\ 0, 0, 0, 1, 0,\\ \end{pmatrix}$$

它表示一个迷宫，其中的$1$表示墙壁，$0$表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为$[0,0]$，既第一格是可以走的路。

数据范围：$2\leq n,m \leq 10$，输入的内容只包含 $0、1$

• 输入描述：

  输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

• 输出描述：

  左上角到右下角的最短路径

示例一

输入：
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出：
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

分析

从迷宫左上角的起点开始，对迷宫进行深度优先遍历，把$1$当作已访问过的点，$0$当作未访问过的点。先尽量“深”地遍历未访问的点，若周围的点都被访问过，则则证明此路不通，回溯到上一个还有未访问的邻接点的点，重新开始深度优先遍历。

对于深度优先遍历的当前点，

• 如果该点未访问过，（如果是回溯到该点，则已访问过，不需要进行这两步）

  • 将该点加入临时路径，该点标记为已访问

  • 如果该点为终点，则当前路径为最终路径

• 如果存在未访问过的邻接点，则按（下、右、上、左）的优先顺序，访问邻接点，即对该邻接点进行递归的深度优先遍历

• 如果邻接点都已访问，则进行回溯

  • 重新修改该点为未访问，将该点弹出临时路径

  • （利用递归自动实现）通过函数栈回到上一个点的遍历访问，查看剩下的优先顺序的邻接点是否未访问，如不存在未访问的，则继续向上一个点回溯，直到回溯到的点还剩有未访问的邻接点，重新开始深度遍历

代码实现

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> final_path; //最终路径

//深度优先搜索，maze为迷宫地图，(n, m)为迷宫矩阵的行、列数，(i, j)为当前访问点，tmp_path为当前路径
void DFS (vector<vector<int>> &maze, int n, int m, int i, int j, vector<pair<int, int>> &tmp_path) {
    tmp_path.push_back({i, j}); //将该点加入临时路径
    maze[i][j] = 1; //将该点标记为已访问
    
    if (i == n-1 && j == m-1) { //如果该点为终点
        final_path = tmp_path; //当前路径为最终路径
        return;
    }
    
    if (i+1 < n && maze[i+1][j] == 0) { //如有下邻接点且未访问过
        DFS(maze, n, m, i+1, j, tmp_path); //深度优先遍历下邻接点
    }
    if (j+1 < m && maze[i][j+1] == 0) { //如有右邻接点且未访问过
        DFS(maze, n, m, i, j+1, tmp_path); //深度优先遍历右邻接点
    }
    if (i-1 >= 0 && maze[i-1][j] == 0) { //如有上邻接点且未访问过
        DFS(maze, n, m, i-1, j, tmp_path); //深度优先遍历上邻接点
    }
    if (j-1 >= 0 && maze[i][j-1] == 0) { //如有左邻接点且未访问过
        DFS(maze, n, m, i, j-1, tmp_path); //深度优先遍历左邻接点
    }
    
    //如果邻接点都已访问，则进行回溯
    maze[i][j] = 0;
    tmp_path.pop_back();
}

int main () {
    int n, m; //矩阵长宽
    while (cin >> n >> m) {
        vector<vector<int>> maze(n, vector<int>(m, 0)); //迷宫地图
        for (int i = 0 ; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> maze[i][j];
            }
        }
        
        vector<pair<int, int>> tmp_path;
        DFS(maze, n, m, 0, 0, tmp_path); //深度优先搜索得迷宫解
        
        for (pair<int, int> point : final_path) {
            cout << "(" << point.first << "," << point.second << ")" << endl;
        }
    }
    return 0;
}

数独游戏

描述

玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9，并且不重复。

例如：(0代表空缺位)

数据范围：输入一个 9*9 的矩阵

• 输入描述：

  包含已知数字的9X9盘面数组（空缺位以数字0表示）

• 输出描述：

  完整的9X9盘面数组

示例一

输入：
0 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
0 4 5 2 7 6 8 3 1
输出：
5 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
9 4 5 2 7 6 8 3 1

示例二

输入：
0 0 8 7 1 9 2 4 5
9 0 5 2 3 4 0 8 6
0 7 4 8 0 6 1 0 3
7 0 3 0 9 2 0 0 0
5 0 0 0 0 0 0 0 0
8 6 1 4 0 3 5 2 9
4 0 0 0 2 0 0 0 8
0 0 0 0 0 0 0 7 0
1 0 7 0 6 8 0 5 0
输出：
6 3 8 7 1 9 2 4 5
9 1 5 2 3 4 7 8 6
2 7 4 8 5 6 1 9 3
7 4 3 5 9 2 8 6 1
5 9 2 6 8 1 4 3 7
8 6 1 4 7 3 5 2 9
4 5 6 3 2 7 9 1 8
3 8 9 1 4 5 6 7 2
1 2 7 9 6 8 3 5 4

分析

深度优先遍历所有的空缺位，对于每个空缺位，

• 找出目前该空缺位所有可能的取值
• 如果存在可能的取值
  • 将可能的取值之一填入
  • 如果当前为最后一个空缺点，且有可能的取值，则求得最终结果
  • 深度优先搜索下一个空缺位
• 如果不存在可能的取值
  • 该位恢复成空缺位
  • 回溯回上一个空缺位，换一个可能的取值

代码实现

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> blank; //空缺位
int final_mp[9][9]; //最终矩阵
bool final_flag = false; //已求得最终矩阵标志

//找到该点可能的取值
vector<int> find_possible_num (int mp[][9], pair<int, int> p) {
    bool flag[9] = {false}; //相应行、列、3X3粗线宫内出现过的数字为true

    int row = p.first, col = p.second; //p所在行、列

    //检验所在行
    for (int j = 0; j < 9; ++j) {
        //如果不是空缺位，且该数字没有出现过
        if (j != col && mp[row][j] != 0 && !flag[mp[row][j] - 1]) {
            flag[mp[row][j] - 1] = true;
        }
    }
    //检验所在列
    for (int i = 0; i < 9; ++i) {
        //如果不是空缺位，且该数字没有出现过
        if (i != row && mp[i][col] != 0 && !flag[mp[i][col] - 1]) {
            flag[mp[i][col] - 1] = true;
        }
    }
    //检验所在3X3粗线宫
    for (int i = (row/3)*3; i < (row/3)*3 + 3; ++i) {
        for (int j = (col/3)*3; j < (col/3)*3 + 3; ++j) {
            //如果不是空缺位，且该数字没有出现过
            if (!(i == row && j == col) && mp[i][j] != 0 && !flag[mp[i][j] - 1]) {
                flag[mp[i][j] - 1] = true;
            }
        }
    }

    vector<int> possible_num;
    for (int i = 0; i < 9; ++i) {
        if (!flag[i]) {
            possible_num.push_back(i+1);
        }
    }

    return possible_num;
}

//深度优先搜索，mp为目前数独表，n_blank为当前求的空缺位序号
void DFS (int mp[][9], int &n_blank) {
    vector<int> possible_num = find_possible_num(mp, blank[n_blank]);
    int row = blank[n_blank].first, col = blank[n_blank].second; //空缺位所在行、列
    bool f = false;
    if (row >= 7 && !f) {
        f = true;
    }

    //依次递归填入可能的值
    for (int num : possible_num) {
        mp[row][col] = num; //将可能的值填入该空缺位
        
        //如果是最后一个空缺位，结束递归遍历
        if (n_blank == blank.size()-1) {
            //将当前矩阵复制到最终矩阵上
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    final_mp[i][j] = mp[i][j];
                }
            }
            final_flag = true;
            return;
        }
        DFS(mp, ++n_blank); //向下一个空缺位深度优先搜索
        
        if (final_flag) { //如已求得最终矩阵，则跳出循环
            break;
        }
    }

    //如果可能的值都不成立，则进行回溯
    mp[row][col] = 0; //恢复空缺位
    n_blank--; //回到上一个空缺位
}

int main () {
    int mp[9][9];

    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            cin >> mp[i][j];
            if (mp[i][j] == 0) { //0表示空缺位
                blank.push_back({i, j}); //将空缺位压入blank中
            }
        }
    }

    int n_blank = 0; //从0号空缺位开始深度优先遍历
    DFS(mp, n_blank);

    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            cout << final_mp[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}