广度优先搜索和深度优先搜索

Breadth First Search & Depth First Search

ZingLix July 27, 2017

在图的使用中,不可避免的就是对图的搜索,最为基础的就是广度优先搜索(Breadth First Search)和深度优先搜索(Depth First Search)。

广度优先搜索

广度优先搜索,又名宽度优先搜索,从根节点开始,沿着宽度遍历整张图,直到所有节点都被访问过为止。在下图可以清楚的看出这一点。

BFS-Ex.gif

在算法中,每一个结点都被涂上一个颜色,白色、灰色和黑色,白色代表尚未发现,灰色代表被发现但尚未检查,颜色即将改变,黑色代表访问完毕。此外利用一个优先队列记录被发现的但未访问完成的节点,即灰色节点。同时,在搜索同时会生成一颗广度优先树,所以对于每个节点都定义一个属性 \(pi\),用以保存前驱结点。

具体实现方法为:

  1. 先初始化,将所有结点涂白,并将前驱节点置为 NULL 。
  2. 先将根节点涂灰,并放入队列中。
  3. 在队列中取出第一个结点 u ,并检查与其相邻的结点 v 。如果 v 为白,则将其涂灰并设置前驱结点,之后将其置入队列。
  4. 结点 u 访问完成,将其涂黑。
  5. 重复步骤 3 ,直到队列为空。

BFS.gif

在上图中,蓝色代表灰色结点(被发现,但未检查),黑色代表白色结点(尚未发现),橙色代表黑色结点(已访问完毕)。

实现代码:

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
// 此代码中以邻接矩阵graph的形式来实现
// 所有结点被存储在数组vertex中,并对每个结点标号 0, 1, 2......,总共 v 个结点
// 函数传进参数 s,表示结点编号

void Graph::BFS(int s) {
  // 步骤 1
    for (int i = 0; i < v; i++) {
        vertex[i].color = WHITE;
        vertex[i].pi = nullptr;
    }
    // 步骤 2
    vertex[s].color = GRAY;
    vertex[s].pi = nullptr;
    std::priority_queue<int> Q;
    Q.push(s);
    while (Q.empty() != true) {          //步骤 5 循环
        // 步骤 3
        int u = Q.top();
        Q.pop();
        for (int i = 0; i < v; i++) {
            if (graph[u][i] != 0) {
                if (vertex[i].color == WHITE) {
                    vertex[i].color = GRAY;
                    vertex[i].pi = &vertex[u];
                    Q.push(i);
                }
            }
        }
        // 步骤 4
        vertex[u].color = BLACK;
    }
}

深度优先搜索

深度优先搜索相对于广度优先而言,顾名思义,会优先沿着一条路走到底,之后再回退,再选择其他的路继续。

DFS-Ex.gif

与广度优先搜索相同,会使用黑白灰三色来标记结点,用 \(pi\) 标记前驱结点以实现深度优先树。

具体实现方法中会涉及两个函数 DFS 和 DFS-Visit ,DFS 中负责初始化和对每一个结点进行搜索,DFS-Visit 则对给定结点进行搜索。

DFS 具体做法为:

  1. 先初始化,将所有节点涂白,并将前驱结点置为 NULL 。
  2. 对所有结点进行遍历,如果结点为白,则对其进行搜索 DFS-Visit 。

DFS-Visit 要求传进一个结点 u ,具体内容为:

  1. 将结点 u 涂灰。
  2. 检查与结点 u 所有相连结点,如果为白,则对其设置前驱结点,再以递归方式对其访问 DFS-Visit 。
  3. 完成后结点 u 访问完毕,将其涂黑。

DFS.gif

颜色含义与广度优先中相同。

具体实现代码:

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
// 此代码中以邻接矩阵graph的形式来实现
// 所有结点被存储在数组vertex中,并对每个结点标号 0, 1, 2......,总共 v 个结点
// 函数传进参数 i,表示结点编号

void Graph::DFS() {
       // 步骤 1
    for (int i = 0; i < v; i++) {
        vertex[i].color = WHITE;
        vertex[i].pi = nullptr;
    }
    // 步骤 2
    for (int i = 0; i < v; i++) {
        if (vertex[i].color == WHITE) {
            DFSVisit(i);
        }
    }
}

void Graph::DFSVisit(int i) {
    // 步骤 1
    vertex[i].color = GRAY;
    // 步骤 2
    for (int j = 0; j < v; j++) {
        if (graph[i][j] != 0) {
            if (vertex[j].color == WHITE) {
                vertex[j].pi = &vertex[i];
                DFSVisit(j);    // 递归方式继续搜索

            }
        }
    }
    // 步骤 3
    vertex[i].color = BLACK;
}

简化

从上述代码中可以看出,在检查一个结点是否访问过时,是以是否为白色为根据,所以黑色与灰色结点在实际实现中作用相同,仅帮助理解之用。同时,如果不使用到生成树的形式,\(pi\) 同样可以被省略。

精简后的 DFS :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 代码中变量定义与之前相同
// visited用以记录结点是否被访问过


void Graph::DFS_Simplified(int s) {
    for (int i = 0; i < v; i++) visited[i] = 0;   // 初始化访问状态
    DFSVisit_Simplified(s);
}

void Graph::DFSVisit_Simplified(int i) {
    visited[i] = 1;
    for (int j = 0; j < v; j++) {
           // 如果与结点 i 相连的结点未被访问,则对其访问
        if (graph[i][j] != 0 && visited[j] == 0) DFSVisit_Simplified(j);
    }
}

图片和gif根据 visualgo.net 制作