C++实现广度优先搜索实例

C++实现广度优先搜索实例攻略

什么是广度优先搜索？

广度优先搜索（Breadth-First Search，也称之为BFS）是一种基于图的搜索算法，用于访问位于某个特定顶点距离为K的所有顶点。它广泛应用于树和图的数据结构中。

BFS的过程如下：

1. 从源节点开始遍历；
2. 访问相邻的节点；
3. 将相邻节点加入队列；
4. 标记已访问的节点；
5. 重复步骤2-4，直到队列为空。

如何用C++实现BFS算法？

以下是用C++实现BFS算法的步骤：

1. 定义一个节点结构体，并用邻接矩阵存储图；
2. 定义一个bool类型的visited数组，用于记录节点是否被访问过；
3. 定义一个queue数据结构，并将起始节点压入队列；
4. 使用while循环遍历队列，对队首节点进行访问；
5. 将队首节点相邻的未被访问的节点加入队列，并将其标记为已访问；
6. 重复步骤4-5，直到队列为空。

示例1：求最短路径

假设有一个无向图（具体定义见代码），其中每条边的距离为1，现在我们要求从节点0到节点5的最短路径。可以使用以下C++代码实现BFS算法：

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

const int MAX = 10;
int graph[MAX][MAX]; // 邻接矩阵存储图
bool visited[MAX]; // 是否已经访问过

int BFS(int start, int end)
{
    queue<int> q;
    int steps = 0;
    q.push(start);
    visited[start] = true;
    while (!q.empty())
    {
        int n = q.size();
        steps += 1;
        for (int i = 0; i < n; i++)
        {
            int cur = q.front();
            q.pop();
            for (int j = 0; j < MAX; j++)
            {
                if (graph[cur][j] == 1 && !visited[j])
                {
                    if (j == end)
                    {
                        return steps;
                    }
                    visited[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return -1; // 没有找到从start到end的路径
}

int main()
{
    // 初始化图
    graph[0][1] = graph[0][3] = 1;
    graph[1][0] = graph[1][2] = graph[2][1] = graph[2][4] = graph[3][0] = graph[3][4] = graph[4][2] = graph[4][3] = graph[4][5] = 1;

    int res = BFS(0, 5);
    cout << "The length of the shortest path from 0 to 5 is:" << res << endl;

    return 0;
}

输出结果为：

The length of the shortest path from 0 to 5 is:3

示例2：迷宫求解

假设有一个迷宫（具体定义见代码），其中0表示可以通行的路径，1表示墙不能通行，现在我们要求从起点[0][0]到终点[2][2]的最短路径。可以使用以下C++代码实现BFS算法：

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

const int MAX = 3;
int maze[MAX][MAX] = {{0,1,0},{0,0,1},{1,0,0}}; // 迷宫
bool visited[MAX][MAX]; // 是否已经访问过
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; // 四个方向

int BFS(int startx, int starty, int endx, int endy)
{
    queue<pair<int, int>> q;
    int steps = 0;
    q.push(make_pair(startx, starty));
    visited[startx][starty] = true;
    while (!q.empty())
    {
        int n = q.size();
        steps += 1;
        for (int i = 0; i < n; i++)
        {
            pair<int, int> cur = q.front();
            q.pop();
            for (int j = 0; j < 4; j++)
            {
                int newx = cur.first + dir[j][0];
                int newy = cur.second + dir[j][1];
                if (newx < 0 || newx >= MAX || newy < 0 || newy >= MAX)
                {
                    continue;
                }
                if (maze[newx][newy] == 0 && !visited[newx][newy])
                {
                    if (newx == endx && newy == endy)
                    {
                        return steps;
                    }
                    visited[newx][newy] = true;
                    q.push(make_pair(newx, newy));
                }
            }
        }
    }
    return -1; // 没有找到从(startx, starty)到(endx, endy)的路径
}

int main()
{
    int res = BFS(0, 0, 2, 2);
    cout << "The length of the shortest path from (0,0) to (2,2) is:" << res << endl;

    return 0;
}

输出结果为：

The length of the shortest path from (0,0) to (2,2) is:2

总结

通过以上示例，我们可以发现，BFS算法可以解决许多基于图结构的问题，如求最短路径、迷宫求解等。在使用C++实现BFS算法时，我们需要定义节点结构体、用邻接矩阵存储图、定义visited数组等，并使用queue数据结构以及while循环来实现算法。