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

广度优先搜索（BFS）

前言

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

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

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

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

基本思路

广度优先搜索的实现思路大致如下：

1. 访问起始节点 v。
2. 从v出发，访问其未被访问的邻接结点$w_1,w_2,w_3...w_n$。
3. 再从被访问过的$w_1,w_2,w_3..,w_n$出发，执行步骤2。
4. 重复步骤2、3，直至与v连通的所有的结点都被访问。

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

那么按照BFS的思路：

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

再执行步骤2，访问 2、4。

执行步骤3：对2，可访问3。对4，3已被2访问过了，跳过。

再对3，1、2都已被访问过了，跳过。

此时得到的搜索序列为：1 2 4 3。

基本实现

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

// C++

#include <queue>

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

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

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

bool visited[MAX_SIZE]; // 访问标记

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

    // ... 访问动作
}

/**
 * BFS算法
 * 
 * 按照广度优先搜索策略访问与起始结点 i 连通的所有结点。
 * 
 * @param {Graph} G 图
 * @param {int} i 起始顶点
 */
void BFS(Graph G, int i){
    // 初始化
    for(int j = 0; j< G.v_num; j++){
        visited[j] = false;
    }
    
    // 访问起始节点
    visit(i);
    
    // 这里借助队列来实现同一个结点后继的访问相邻。
    std::queue<int> q;
    q.push(i);

    while(!q.empty()){
        int cur = q.front();
        q.pop();

        for(int j=0; j< G.v_num; j++){
            // 如果边存在，且未被访问，则访问并加入队列q。
            if(!visited[j] && G.edge[cur][j] == 1) {
                visit(j);
                q.push(j);
            }
        }
    }
}

BFS的应用

判断图的连通性

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

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

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

图的遍历

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

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

图的广度优先遍历的思路如下：

1. 访问起始节点 v。
2. 从v出发，访问其未被访问的邻接结点$w_1,w_2,w_3...w_n$。
3. 再从被访问过的$w_1,w_2,w_3..,w_n$出发，执行步骤2。
4. 重复步骤2、3，直至与v的连通的所有的结点都被访问。
5. 从剩余未被访问的结点中任选一个结点，执行操作1到4，直至所有结点都被访问。

/**
 * @param {Graph} G 需要遍历的图
 */
void BFSTraverse(Graph G){
    // 初始化
    for(int j = 0; j< G.v_num; j++){
        visited[j] = false;
    }
    
    // 操作5
    for(int i = 0;i<G.v_num; i++){
        if(!visited[i]) BFS(G, i);
    }
}

/**
 * BFS算法
 * 
 * 按照广度优先搜索策略访问与起始结点 i 连通的所有结点。
 * 
 * @param {Graph} G 图
 * @param {int} i 起始顶点
 */
void BFS(Graph G, int i){
    // 初始化
    // for(int j = 0; j< G.v_num; j++){
    //     visited[j] = false;
    // }
        
    // 访问起始节点
    visit(i);
    
    // 这里借助队列来实现同一个结点后继的访问相邻。
    std::queue<int> q;
    q.push(i);

    while(!q.empty()){
        int cur = q.front();
        q.pop();

        for(int j=0; j< G.v_num; j++){
            // 如果边存在，且未被访问，则访问并加入队列q。
            if(!visited[j] && G.edge[cur][j] == 1) {
                visit(j);
                q.push(j);
            }
        }
    }
}

求单源最短路径

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

这一特性就使得在首次访问到终点时，从起点到达终点的路径必然是最短的。

例如：

从 1 -> 4的路径有

• 1 -> 2 -> 4
• 1 -> 2 -> 3 ->4
• 1 -> 3 -> 4
• 1 -> 3 -> 5 -> 7 -> 4
• 1 -> 3 -> 5 -> 6 -> 7 -> 4

按照BFS的遍历顺序，那么在对2执行操作2时，就会第一次遇到4号结点，它们之间的路径是2。

代码实现

int dis[MAX_SIZE];

/**
 * BFS计算从u结点出发到图中任意结点的最短路径
 * 
 * @param {Graph} G
 * @param {int} u
 */
void get_min_distance(Graph G, int u)
{
    // 初始化
    for (int i = 0; i < G.v_num; i++)
    {
        dis[i] = -1;
        visited[i] = false;
    }

    visited[u] = true;
    dis[u] = 0;

    std::queue<int> q;
    q.push(u);

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        for (int j = 0; j < G.v_num; j++)
        {
            if (!visited[j] && G.edge[cur][j] == 1)
            {
                visited[j] = true;
                dis[j] = dis[cur] + 1;
                q.push(j);
            }
        }
    }
}

全篇至此结束，感谢阅读！