掌握使用 C++ 实现图的 BFS 遍历

介绍

在本实验中，你将学习如何使用 C++ 实现图的广度优先搜索（BFS）遍历算法。BFS 算法从图中的一个节点开始，先探索当前深度的所有节点，然后再移动到下一层的节点。BFS 遍历利用了称为队列（Queue）的数据结构。我们也将详细解释队列数据结构。

项目设置

导航到 project 目录：

cd project

使用以下命令创建一个名为 main.cpp 的 C++ 文件：

touch main.cpp

引入必要的库

在 C++ 中，我们使用 iostream 来处理输入和输出，使用 vector 来动态存储元素，并使用 queue 来实现 BFS 遍历算法。我们还使用 bits/stdc++.h 头文件来包含所有标准库。在 main.cpp 文件中，输入以下代码：

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<bool> v;
vector<vector<int>> g;

实现 BFS 遍历算法

我们将创建一个名为 bfsTraversal 的函数，该函数以起始节点作为参数。此函数将处理 BFS 遍历算法。

void bfsTraversal(int b)
{
    queue<int> q; // 声明一个队列来存储与 b 连接的所有节点
    q.push(b); // 将 b 插入队列
    v[b] = true; // 将 b 标记为已访问

    cout << "\n\nThe BFS Traversal is:  ";

    while (!q.empty())
    {
        int a = q.front();
        q.pop(); // 从队列中删除第一个元素

        // 遍历与当前节点连接的所有节点
        for (auto j = g[a].begin(); j != g[a].end(); j++)
        {
            if (!v[*j])
            {
                v[*j] = true;
                q.push(*j); // 将连接的节点添加到队列中以进行处理
            }
        }
        cout << a << "  ";
    }
}

向图中添加边

我们将创建一个名为 makeEdge 的函数，该函数接收两个顶点并在它们之间创建一条边。该函数将为图的每条边调用。

void makeEdge(int a, int b)
{
    g[a].push_back(b); // 从顶点 a 到顶点 b 的一条边
}

接收图信息

在这一步中，我们将从用户那里接收图的信息，包括顶点数、边数、边的源顶点和目标顶点，并初始化向量。

int main()
{
    int n, e, a, b, i;

    cout << "Enter the number of vertices: ";
    cin >> n;

    cout << "Enter the number of edges: ";
    cin >> e;

    v.assign(n, false);
    g.assign(n, vector<int>());

    cout << "Enter the edges with source and target vertex: ";

    for (i = 0; i < e; i++)
    {
        cin >> a >> b;
        makeEdge(a, b);
    }

    for (i = 0; i < n; i++)
    {
        if (!v[i])
        {
            bfsTraversal(i);
        }
    }

    return 0;
}

编译并运行程序

下一步是编译并运行代码。在终端中运行以下命令：

g++ main.cpp -o main && ./main

你应该能够在终端中看到图的 BFS 遍历算法的输出。

`main.cpp` 文件的完整代码

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<bool> v;
vector<vector<int>> g;

void bfsTraversal(int b)
{
    queue<int> q;
    q.push(b);
    v[b] = true;

    cout << "\n\nThe BFS Traversal is:  ";

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

        for (auto j = g[a].begin(); j != g[a].end(); j++)
        {
            if (!v[*j])
            {
                v[*j] = true;
                q.push(*j);
            }
        }
        cout << a << "  ";
    }
}

void makeEdge(int a, int b)
{
    g[a].push_back(b);
}

int main()
{
    int n, e, a, b, i;

    cout << "Enter the number of vertices: ";
    cin >> n;

    cout << "Enter the number of edges: ";
    cin >> e;

    v.assign(n, false);
    g.assign(n, vector<int>());

    cout << "Enter the edges with source and target vertex: ";

    for (i = 0; i < e; i++)
    {
        cin >> a >> b;
        makeEdge(a, b);
    }

    for (i = 0; i < n; i++)
    {
        if (!v[i])
        {
            bfsTraversal(i);
        }
    }

    return 0;
}

总结

在本实验中，你学习了如何使用 C++ 在图上实现 BFS 遍历算法。该算法从起始节点开始，探索图中的所有节点。我们使用队列数据结构来实现 BFS 算法。通过完成本实验，你对图遍历算法有了更深入的理解。

在图上实现 BFS 遍历

介绍