【数据结构与算法】深度优先搜索（DFS）

深度优先搜索（DFS）

对于考研人来说，BFS和DFS指的是图的两种遍历算法。

但是严格意义上说，BFS和DFS是两种搜索策略。

• BFS代表算法在执行时，会像树的层次遍历那样，从属于同一个结点的后继的访问顺序相邻。

• DFS代表算法在执行时，会像树的先序遍历那样，沿着某条路径走到终点，再返回走另外一条路径。

基本思路

DFS的实现思路如下：

1. 访问起始结点v。
2. 从起始结点v出发，访问v的任意一个未被访问的邻接结点w1，再访问w1的任意一个未被访问邻接结点w2，再访问w2的任意一个未被访问的邻接结点w3…以此类推，直至无法继续向下访问。
3. 当无法继续向下访问时，回到最近被访问的顶点，若它存在邻接结点未被访问过，则以该结点作为起始结点执行操作2。
4. 重复2-3直至所有顶点都被访问。

例如，现在有一个有向图：

那么按照DFS的思路：

假设从1开始搜索，那么先访问 1。

再执行步骤2，可以得到序列 2 -> 3。此时3无法继续访问。

再执行步骤3，返回到2，但是2无邻接结点未被访问，返回到1，1有一个邻接结点4，执行步骤2，得到序列 4。

综上，按照DFS得到的搜索序列为 1 2 3 4。

基本实现

DFS这种访问，然后回退的方式，非常地契合递归原理。因此DFS常常使用递归实现。（非递归方式可以借助栈来实现，但是递归方式本质上也是一个栈）

这里我们基于邻接矩阵实现DFS，如果有感兴趣的同学，可以实现一下基于邻接表的DFS算法。

const int MAX_SIZE = 100; // 最大容量

struct Graph
{
    VT vex[MAX_SIZE];             // 顶点集
    int edge[MAX_SIZE][MAX_SIZE]; // 边集

    int v_num; // 当前顶点个数
};

bool visited[MAX_SIZE];

/**
 * 访问结点
 */
void visit(int i)
{
    // 标记已被访问
    visited[i] = true;

    // ... 访问动作
}


/**
 * DFS的递归实现
 * 
 * 执行DFS前需要先初始化visited[]。
 * 按照深度优先的顺序遍历所有与i连通的结点。
 * 
 * @param {Graph} G 图
 * @param {int} i 起始顶点
 */
void DFS(Graph G, int i)
{
    visit(i);
    for (int j = 0; j < G.v_num; j++)
    {
        if (G.edge[i][j] == 1 && visited[j] == false)
        {
            DFS(G, j);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

DFS的应用

判断图的连通性

对于无向图来说，若图是连通的，那么从任意一个结点出发，执行一遍BFS搜索即可访问到图中的所有结点。

对于有向图来说，若图是强连通的，那么和无向图一样，从任意一个结点出发，执行一遍DFS也能够访问到图中的所有结点。

因此DFS可以用来判断图的连通性，从任意一个结点出发执行一遍DFS，统计访问到的结点个数，与图中所有结点的个数进行比较，即可实现判断。

图的遍历

由于并不是所有的图都是连通图，因此，在DFS的基础上，我们还需要保证图中的每一个结点都被访问到。

因此，我们还需要添加一个操作，来实现遍历图中的每一个结点：

1. 访问起始结点v。
2. 从起始结点v出发，访问v的任意一个未被访问的邻接结点w1，再访问w1的任意一个未被访问邻接结点w2，再访问w2的任意一个未被访问的邻接结点w3…以此类推，直至无法继续向下访问。
3. 当无法继续向下访问时，回到最近被访问的顶点，若它存在邻接结点未被访问过，则以该结点作为起始结点执行操作2。
4. 重复2-3直至所有顶点都被访问。
5. 从剩余未被访问的结点中任选一个结点，执行操作1到4，直至所有结点都被访问。

// C++

void DFSTraverse(Graph G){
    // 初始化
    for (int j = 0; j < G.v_num; j++)
    {
        visited[j] = false;
    }

    for(int i=0; i<G.v_num; i++){
        if(!visited[i]) DFS(G, i);
    }
}

void DFS(Graph G, int i)
{
    visit(i);
    for (int j = 0; j < G.v_num; j++)
    {
        if (G.edge[i][j] == 1 && visited[j] == false)
        {
            DFS(G, j);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

暴力枚举

根据DFS的思路，算法在执行的时候实际上就是在尝试每一种可能的情况。因此DFS又叫暴力搜索算法。它能够解决一些形如排列组合之类的需要枚举所有情况的问题。

代码的大致格式如下：

void dfs(int step)
{
        判断是否符合条件
        {
            相应操作
        }
        
        枚举每一种可能
        {
               标记 //防止多次重复枚举同一个方案
               继续下一步dfs(step+1)
               恢复初始状态 //恢复现场
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

判断图中是否有环（回路）

按照DFS的规则，一个结点在访问完其所有相邻节点之后，会从当前结点的父节点回溯到下一个未被访问的相邻结点。如果一个结点已经被访问过，那么它应该已经在集合中，等待回溯。但是，如果这个结点再次被访问，就说明存在一个路径可以从这个结点直接回溯到其父结点，形成一个回路。

所以我们可以通过DFS来判断图中是否存在回路。

全篇结束，感谢阅读！