Продолжаю решать задачи на веб-сервисе «CodeRun» от «Яндекса» (предыдущие посты в этой серии: 1, 2). В этот раз опишу, как решил задачу из группы «легких», которая называется «Длина кратчайшего пути».

Формулировка задачи

Дан неориентированный граф. Найти длину минимального пути между двумя заданными вершинами этого графа.

Первым при вводе данных получить количество N вершин в графе. Число N находится в диапазоне от 1 до 100, включая границы. Далее получить матрицу смежности — таблицу размерами N × N, в ячейках которой содержатся числа 0 или 1. В последнюю очередь получить номера начальной и конечной вершин. Вершины нумеруются с единицы.

Вывести число — длину кратчайшего пути (минимальное количество ребер, которые нужно пройти). Если пути не существует, вывести число -1.

Пример ввода данных и вывода результата:

5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
3

В первой строке здесь введено количество вершин в графе — 5. Далее введена матрица смежности, то есть таблица размерами 5 × 5, в ячейках которой содержатся числа 0 или 1. После матрицы смежности введены числа 3 и 5 — номера начальной и конечной вершин соответственно. В последней строке программа вывела результат своей работы — число 3. То есть при заданных данных длина кратчайшего пути от вершины 3 к вершине 5 — 3 ребра.

Графы и связанные с ними термины

Граф — это очень известный в математике и программировании инструмент моделирования. Графом можно представить много чего из реальной жизни. Например, графом можно представить систему дорог в городе или стране. Это используется, к примеру, для написания программ автомобильных навигаторов и тому подобного.

Существует большое количество разных видов графов, для обозначения которых используют разные термины. Во всех графах есть вершины (узлы, vertices, в единственном числе — vertex) и ребра (edges).

Вершины обычно обозначают буквами или числами. В данном случае удобнее для этого использовать числа, что я и буду делать. На рисунке вершины обычно представляют кружками. Номера вершин я буду писать внутри этих кружков.

Ребра — это линии, каждая из которых соединяет две вершины графа. Обычно ребро соединяет две разные вершины. Но бывают ребра, которые выходят из вершины и входят в нее же (петли).

Ребра бывают с направлением (ребро изображается в виде линии со стрелкой) и без направления (ребро изображают в виде линии). Если в графе все ребра без направления, то граф называют неориентированным.

Ребра в графах бывают с весами, то есть около ребра в этом случае пишут его вес — некое число. Графы с такими ребрами называют взвешенными. В нашем случае подразумевается, что у ребер графа нет весов. Такой граф называют невзвешенным. Думаю, автору задачи следовало бы указать в формулировке задачи и этот термин тоже.

Матрица смежности и рисунок графа

Когда нужно представить граф числами, чтобы передать его для обработки в программу, часто используют так называемую матрицу смежности. В графе две вершины считаются смежными, если они соединены ребром. Наверное, можно было бы назвать матрицу смежности «матрицей соединенности вершин», так как в этой матрице показано, как вершины соединены между собой ребрами.

Если в графе нет петель (ребер, выходящих из вершины и входящих в нее же), то главная диагональ (из левого верхнего угла в нижний правый угол) матрицы смежности состоит из нулей (в матрице смежности число 0 означает отсутствие ребра, а число 1 — наличие ребра).

Я нарисую для наглядности граф, представленный матрицей смежности из формулировки задачи. Этот граф состоит из пяти вершин, обозначенных числами от 1 до 5 включительно.

Матрицу смежности можно интерпретировать, заходя с двух сторон. Например, первая строка матрицы смежности содержит информацию о соединениях вершины 1 со всеми другими вершинами. С другой стороны, первый столбец матрицы смежности тоже содержит ту же информацию. Из-за этого получается, что в матрице смежности ее половина ниже главной диагонали «зеркалит» ее половину выше главной диагонали. Такие матрицы еще называют симметричными. (Описанное тут относится к неориентированным невзвешенным графам без петель, то есть это не универсальные для всех графов утверждения.)

При необходимости экономить память можно было бы хранить в памяти только одну из описанных выше треугольных половинок матрицы смежности. Другую такую половинку матрицы смежности можно всегда восстановить из имеющейся. Но в нашем случае это не требуется.

Вот какой получился рисунок графа (для рисования использовал веб-сервис https://programforyou.ru/graph-redactor, тут — формат SVG):

На этом рисунке видно, что путь от вершины 3 до вершины 5 действительно составляет 3 ребра, как и показано в примере в формулировке задачи. Кстати, этот рисунок показывает, что существуют графы, в которых одна или ряд вершин не соединены с другими вершинами ребрами (тут это вершина 4). Такие вершины называют изолированными. Если пользователь захочет узнать длину кратчайшего пути, например, из вершины 3 в вершину 4, то программа должна вывести в качестве результата число -1 (путь не существует).

Обход и поиск в ширину

Автор задачи поставил на нее метку «bfs». В данном случае аббревиатура BFS расшифровывается как «breadth-first search», по-русски «поиск в ширину».

Если вы используете в программе структуру данных, в которой есть вершины (хранилища каких-либо значений) и связи между этими вершинами (можно реализовать с помощью указателей), то первая задача, которая встанет перед вами — это как обходить вершины такой структуры данных. Такой обход может понадобиться для разных целей, например: вывод всех значений структуры данных в консоль, добавление нового значения, поиск конкретного значения, удаление конкретного значения и так далее.

Когда вы используете линейную структуру данных, вроде массива, такого вопроса не возникает: чаще всего элементы массива обходят по порядку от первого (нулевого) до последнего. Граф — это нелинейная структура данных, то есть из любого элемента (вершины) может выходить несколько путей (ребер), поэтому количество способов обхода элементов заведомо больше одного. Приходится выбирать.

Насколько я понимаю, «Обходом в ширину» графа называют такой обход вершин, при котором сначала обходят все вершины, соединенные с начальной одним ребром, то есть ближайшие вершины. После этого обходят все вершины, соединенные с начальной двумя ребрами, и так далее. «Обходом в ширину» такой обход называют потому, что обработанная область графа равномерно увеличивается вширь.

Если при обходе графа в ширину стоит задача найти конкретную вершину, такой обход в ширину называют «поиском в ширину». При поиске в ширину обход графа прекращается, как только найдена искомая вершина графа. Часть графа при этом остается необработанной.

Почему мы здесь выбираем именно алгоритм поиска в ширину? Сам этот алгоритм позволяет только найти нужную вершину. Однако, то, как происходит обработка вершин в графе при использовании этого алгоритма (в ширину), является очень удобным для нахождения длины кратчайшего пути к любой вершине, в том числе к искомой. Но для нахождения этой длины кратчайшего пути понадобится добавление специального кода.

В моем представлении любой алгоритм обхода графа — это что-то вроде рамы (платформы), на которую можно вешать разный дополнительный код в зависимости от того, что нам требуется в данный момент.

Реализация поиска в ширину на C++

Я взял неформальное (словесное) описание алгоритма поиска в ширину из википедии и переформулировал его так, как мне было удобнее:

  1. Создать пустую очередь и поместить в нее номер начальной вершины.

  2. В цикле с постусловием:

    • извлечь из очереди очередной номер вершины и пометить его как развернутый (посещенный);

    • если эта вершина является искомой, то завершить поиск с результатом «успех»;

    • в противном случае добавить в очередь всех потомков следующего поколения этой вершины, если они еще не развернуты (не посещены) и не находятся в очереди.

  3. Если очередь не пуста, вернуться к пункту 2.

  4. Если цикл пройден без результата «успех», значит искомый (конечный) узел недостижим из начального узла.

На анимированных иллюстрациях к этому алгоритму (в википедии и не только) можно увидеть, что процесс работы этого алгоритма демонстрируется закрашиванием вершин графа разными цветами. При этом обычно в начале все вершины графа закрашены белым цветом; это означает, что все вершины пока что не обработаны.

Обработка вершины начинается с того, что она попадает в очередь (структура данных, в которую данные помещают с одного конца, а извлекают с другого). На иллюстрации попадание в очередь отображается закрашиванием вершины обычно серым цветом.

Окончание обработки вершины происходит после извлечения этой вершины из очереди. При этом данная вершина на иллюстрации помечается обычно черным цветом. Такую вершину еще называют «развернутой» или «посещенной».

Существуют еще структуры данных, которые называют «деревьями». Дерево — это частный случай графа. Дерево отличается тем, что в нем не разрешаются так называемые «циклы», то есть существование закольцованных путей. Если вы работаете с деревом, то алгоритм поиска в ширину упрощается: нет необходимости помечать посещенные (развернутые) вершины. Если речь идет про граф, как в нашей задаче, пометка посещенных вершин необходима, чтобы не попасть в бесконечный цикл, если в графе существуют закольцованные пути.

Для запоминания посещенных вершин я создал специальный массив visited с количеством элементов, равным количеству вершин графа, и с типом элементов bool. Этот массив создаю и инициализирую до начала цикла с постусловием из пункта 2 алгоритма.

Поскольку цикл из пунктов 2 и 3 можно пройти с «успехом» (искомая вершина найдена) и без «успеха» (искомая вершина не найдена), я решил использовать переменную-флаг path_exists типа bool, которая станет равна true, если искомая вершина найдена, и останется равна false, если искомая вершина не найдена.

Получение длины кратчайшего пути

Как я упоминал выше, поиск в ширину удобен для нахождения кратчайшего пути между двумя вершинами, но по умолчанию предназначен только для поиска конечной вершины из начальной.

Чтобы найти кратчайший путь между двумя заданными вершинами, я создал так называемый «массив предков», который называл parent. Этот массив я создаю до цикла с постусловием из пункта 2 алгоритма. Он содержит элементы типа int в количестве, совпадающим с количеством вершин в графе. Индекс элемента в этом массиве является номером вершины графа, а значение элемента — номер вершины-родителя для данной вершины.

Массив parent я заполняю при добавлении вершины графа в очередь в пункте 2 алгоритма. Изначально все элементы этого массива инициализирую значением -1, которое означает, что у данной вершины вообще нет родителя, либо родитель пока неизвестен.

После окончания цикла с постусловием, то есть после пункта 3 алгоритма, я запускаю еще один цикл по массиву parent, в котором прохожу от конечной (искомой) вершины по записанным родителям к начальной вершине. Количество шагов в этом цикле и есть длина кратчайшего пути от начальной вершины к конечной (искомой).

Полный код программы на языке C++

В качестве массива использую std::vector. В качестве очереди использую std::queue.

Как я понял, для очереди std::queue не существует метода, с помощью которого можно было бы определить, содержится ли заданный элемент в данной очереди. Пришлось написать для этого отдельную функцию, которую я назвал isInQueue. Эту функцию можно реализовать по-разному.

Я для этого копирую существующую очередь (очередь передается в функцию «по значению», при этом происходит ее копирование) и начинаю в цикле удалять из очереди элементы. Если очередной элемент является искомым, то он содержится в очереди-оригинале. Если же цикл заканчивается, а искомый элемент не найден, он не содержится в очереди-оригинале.

#include <iostream>
#include <vector> // для std::vector
#include <queue>  // для std::queue

bool isInQueue(std::queue<int> q, int v)
{
    while (!q.empty())
    {
        if (q.front() == v) return true;
        q.pop();
    }
    return false;
}

int main()
{
    // получить количество вершин в графе,
    // по условиям задачи это число в диапазоне [1..100]
    int N{};
    std::cin >> N;

    // получить матрицу смежности edges размером N × N,
    // в ней должны быть только числа 0 (нет ребра) и 1 (есть ребро)
    std::vector<std::vector<int>> edges(N, std::vector<int>(N, 0));
    for (int r{}; r < N; r++)
        for (int c{}; c < N; c++)
            std::cin >> edges[r][c];

    // получить номера начальной и конечной вершин
    int begV{};
    int endV{};
    std::cin >> begV;
    std::cin >> endV;
    // привести пользовательскую нумерацию (с единицы) к нумерации с нуля
    begV--;
    endV--;

    // создать пустую очередь и поместить в нее номер начальной вершины
    std::queue<int> q;
    q.push(begV);
    // создать массив посещенных вершин и массив родителей
    std::vector<bool> visited(N, false); // все вершины пока не посещены
    std::vector<int> parent(N, -1);      // родители не найдены или их нет

    // выполнить поиск конечной вершины по алгоритму "поиска в ширину"
    bool path_exists{ false }; // путь к конечной вершине пока не найден
    do
    {
        // извлечь из очереди узел и пометить его как посещенный
        int curV{ q.front() };
        q.pop();
        visited[curV] = true;

        // если извлеченный узел является искомым
        if (curV == endV)
        {
            path_exists = true; // путь найден,
            break;              // прервать поиск
        }
        else // извлеченный узел НЕ является искомым
        {
            // добавить в очередь всех потомков извлеченного узла,
            // которые еще не посещены и не находятся в очереди
            for (int v{}; v < N; v++)
            {
                if (edges[curV][v] == 1 && !visited[v] && !isInQueue(q, v))
                {
                    q.push(v);        // поместить потомка в очередь,
                    parent[v] = curV; // запомнить для него родителя
                }
            }
        }
    }
    while (!q.empty());

    if (path_exists) // если путь найден
    {
        // восстановить путь, подсчитывая его длину
        int path_len{};
        for (int v{ endV }; parent[v] != -1; v = parent[v])
        {
            path_len++;
        }
        // вывести результат
        std::cout << path_len << '\n';
    }
    else             // путь НЕ найден
    {
        std::cout << -1 << '\n';
    }

    return 0;
}

Выводы

Задача требует знания и понимания терминов из теории графов. Получилось изучить алгоритм обхода (поиска) в ширину и методы его расширения для разных задач.

Как я писал в предыдущих постах, некоторые задачи из группы «легких» на сайте «CodeRun» можно было бы обозначить как «легко-средние»; я думаю, это одна из таких задач.