【算法】广度优先搜索

【算法】广度优先搜索

Richard

2019 年 04 月 06 日

718 次浏览

暂无评论

3512字数

数据结构与算法

广度优先搜索(BFS, Breadth-First Search)也是搜索的手段之一。它与深度优先搜索相似，都是从一个状态出发探索所有可以达到的状态。

BFS 和 DFS不同的地方在于搜索的顺序。DFS是不撞南墙不回头，而BFS就像渗透一样从一个点渗透整个面。

1.算法思想

广度优先搜索思想：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

2.算法特点

广度优先搜索类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。

3.算法过程

3.1 无向图的广度优先搜索

以下列无向图为例，采用广度优先搜索过程。

选取A为起始点，输出A，A入队列，标记A，当前位置指向A。
队列头为A，A出队列。A的邻接顶点有B、E，输出B和E，将B和E入队，并标记B、E。当前位置指向A。
队列头为B，B出队列。B的邻接顶点有C、D，输出C、D，将C、D入队列，并标记C、D。当前位置指向B。
队列头为E，E出队列。E的邻接顶点有D、F，但是D已经被标记，因此输出F，将F入队列，并标记F。当前位置指向E。
队列头为C，C出队列。C的邻接顶点有B、D，但B、D均被标记。无元素入队列。当前位置指向C。
队列头为D，D出队列。D的邻接顶点有B、C、E，但是B、C、E均被标记，无元素入队列。当前位置指向D。
队列头为F，F出队列。F的邻接顶点有G、H，输出G、H，将G、H入队列，并标记G、H。当前位置指向F。
队列头为G，G出队列。G的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向G。
队列头为H，H出队列。H的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向H。
队列空，则以A为起始点的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。

3.2 有向图的广度优先搜索

以下面的有向图为例

选取A为起始点，输出A，将A入队列，标记A。
队列头为A，A出队列。以A为尾的边有两条，对应的头分别为B、C，则A的邻接顶点有B、C。输出B、C，将B、C入队列，并标记B、C。
队列头为B，B出队列。B的邻接顶点为C，C已经被标记，因此无新元素入队列。
队列头为C，C出队列。C的邻接顶点有E、F。输出E、F，将E、F入队列，并标记E、F。
队列头为E，E出队列。E的邻接顶点有G、H。输出G、H，将G、H入队列，并标记G、H。
队列头为F，F出队列。F无邻接顶点。
队列头为G，G出队列。G无邻接顶点。
队列头为H，H出队列。H邻接顶点为E，但是E已被标记，无新元素入队列。
队列为空，以A为起始点的遍历过程结束，此时图中仍有D未被访问，则以D为起始点继续遍历。选取D为起始点，输出D，将D入队列，标记D。
队列头为D，D出队列，D的邻接顶点为B，B已被标记，无新元素入队列。
队列为空，且所有元素均被访问，广度优先搜索遍历过程结束。广度优先搜索的输出序列为：A->B->E->C->D->F->G->H。

4.算法分析

假设图有V个顶点，E条边，广度优先搜索算法需要搜索V个节点，时间消耗是O(V)，在搜索过程中，又需要根据边来增加队列的长度，于是这里需要消耗O(E)，总得来说，效率大约是O(V+E)。

5.经典例题

AC代码（好久之前写的代码，写的不好请轻喷）

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;

int row[36][36];//存原始图 
bool check[36][36];//存连通块 

inline int Input()
{//输入 
    int n;

    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> row[i][j];

    return n;
}

inline void BFS(int n)
{//广搜，n 为起始点 
    queue<P> q;

    for (int i = 0; i < n; i++)
    {//检测周围一圈是否有0，有的话就加入队列 
        if (!row[0][i])
        {
            check[0][i] = true;
            q.push(P(0, i)); 
        }

        if (!row[n - 1][i])
        {
            check[n - 1][i] = true;
            q.push(P(n - 1, i));
        }

        if (!row[i][0])
        {
            check[i][0] = true;
            q.push(P(i, 0));
        }

        if (!row[i][n - 1])
        {
            check[i][n - 1] = true;
            q.push(P(i, n - 1));
        }
    }

    while (!q.empty())
    {
        int x = q.front().first, y = q.front().second;

        q.pop();
        check[x][y] = true;//将起点标记 
        
        for (int i = -1; i <= 1; i++)
        {
            int mx = x + i, my = y + i;
            
            /*检测起点四周是否有符合条件的点，有就加入队列*/ 
            if (mx >= 0 && mx < n && !check[mx][y] && !row[mx][y])
                q.push(P(mx, y));

            if (my >= 0 && my < n && !check[x][my] && !row[x][my])
                q.push(P(x, my));
        }
    }

    return;
}

inline void print(int n)
{//输出 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (check[i][j] || row[i][j] == 1)
                cout << row[i][j];
            else
                cout << "2";

            if (j != n - 1)
                cout << " ";
        }

        cout << endl;
    }

    return;
}

int main()
{
    int n = Input();
    BFS(n);
    print(n);
    //system("pause");
    return 0;
}

参考文章：
《算法竞赛入门经典》
小小吴师兄的文章

【算法】广度优先搜索