bfs

#include <iostream>
using namespace std;

const int n = 4;

//матрица смежности графа
int GM[n][n] =
{
{0, 1, 1, 0},
{0, 0, 1, 1},
{1, 0, 0, 1},
{0, 1, 0, 0}
};

//поиск в ширину
// unit - номер графа с которого начинаем обход
// visited - массив, где индекс - номер узла, а значение - посещали или нет этот узел
void BFS(bool* visited, int unit)
{
    // Очередь в которой будут хранится индексы тех, кого будем посещать
    int* queue = new int[n];


    int count, head;

    for (int i = 0; i < n; i++)
        queue[i] = 0;

    // количество тех, что надо пройти
    count = 0;
    // номер того, по которому идём (исключителньо итерационный номер)
    head = 0;

    // Первый в очереди - тот, с которого начинаем обход (параметр функции)
    queue[count] = unit;
    // Прибавляем 1 к количеству тех, которые надо пройти
    count++;
    // Говорим, что мы по факту посетили 1й узел
    visited[unit] = true;

    // Пока текущий посещённый меньше чем количество тех, что надо посетить
    while (head < count)
    {
        // Присваем значение в очереди по текущему номеру
        unit = queue[head];
        // переходим на следующий номер
        head++;
        // Выводим значение (номер узла) + 1 ( для красоты *исключить нумерацию с 0*)
        cout << unit + 1 << " ";
        // Идём по строчке с номером полученным из очереди
        for (int i = 0; i < n; i++){
            // Если у узла есть связь с другим узлом ( != 0 ) и он ещё не посещался ( visited = false)
            if (GM[unit][i] != 0 &&  visited[i] == false)
            {
                // добавляем его в очередь
                queue[count] = i;
                // Увеличиваем количество тех, что нужно пройти
                count++;
                // И говорим, что посетим (ли)
                visited[i] = true;
            }
        }
    }
    // удаляем массив
    delete[] queue;
}

int main()
{
    setlocale(LC_ALL, "Rus");

    int start;
    cout << "Стартовая вершина >> ";
    cin >> start;

    bool* visited = new bool[n];

    cout << "Матрица смежности графа: " << endl;
    for (int i = 0; i < n; i++)
    {
        visited[i] = false;
        for (int j = 0; j < n; j++)
            cout << " " << GM[i][j];
        cout << endl;
    }

    cout << "Порядок обхода: ";
    BFS(visited, start - 1);

    delete[]visited;

    return 0;
}