Реализация обхода в ширину (BFS) на графе

Введение

В этом лабе вы научитесь реализовывать алгоритм обхода в ширину (BFS) для графа на C++. Алгоритм BFS начинается с узла в графе и исследует все узлы на текущем уровне глубины, прежде чем переходить к узлам на следующем уровне. Обход в ширину использует структуру данных, называемую Очередью. Мы также детально объясним структуру данных Очередь.

Настройка проекта

Перейдите в директорию project:

cd project

Создайте новый файл на C++, названный main.cpp, используя:

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, которая будет принимать начальный узел в качестве аргумента. Эта функция будет обрабатывать алгоритм обхода в ширину.

void bfsTraversal(int b)
{
    queue<int> q; // Объявим очередь для хранения всех узлов, соединенных с b
    q.push(b); // Вставим b в очередь
    v[b] = true; // Отметим b как посещенный

    cout << "\n\nОбход в ширину:  ";

    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 << "Введите количество вершин: ";
    cin >> n;

    cout << "Введите количество ребер: ";
    cin >> e;

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

    cout << "Введите ребра с исходной и целевой вершиной: ";

    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\nОбход в ширину:  ";

    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 << "Введите количество вершин: ";
    cin >> n;

    cout << "Введите количество ребер: ";
    cin >> e;

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

    cout << "Введите ребра с исходной и целевой вершиной: ";

    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;
}

Резюме

В этом лабе вы узнали, как реализовать алгоритм обхода в ширину (BFS) на графе с использованием C++. Алгоритм начинается с начального узла и исследует все узлы графа. Мы использовали структуру данных очередь для реализации алгоритма BFS. Завершив этот лаб, вы приобрели более глубокое понимание алгоритмов обхода графов.