14. Теория графов. Поиск в ширину (BFS).

1. Теория графов. Поиск в ширину (BFS).

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

Условие задачи: Есть N городов. Некоторые из этих городов могут быть попарно связаны друг с другом дорогами. Всего дорог М. Каждая дорога связывает два города и имеет длину (в километрах). Необходимо ответить на вопрос, можно ли проехать по имеющимся дорогам из города X в город Y, и, если да, то какое минимальное количество километров между городами надо проехать.

Исходные данные: Сначала вводится N – количество городов.
Затем М – количество дорог.
Далее для каждой дороги вводится номер города, из которого она идет, номер города, в который она идет, и расстояние в километрах. Города нумеруются, начиная с 0.
Потом вводится Х – номер города, из которого планируется начать движение.
И Y – номер города, в котором планируется закончить движение.

Выводится текст «Дороги нет!», если попасть из города Х в город Y по имеющимся дорогам нельзя или число – минимальное количество километров, которые надо проехать между городами, чтобы попасть из горда Х в город Y.

Мы будем использовать один из основных алгоритмов на графах - поиск в ширину.

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

2. Поиск в ширину (BFS). Описание алгоритма.

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

На вход алгоритма подаётся заданный граф (невзвешенный), и номер стартовой вершины Х. Граф может быть как ориентированным, так и неориентированным, для алгоритма это не важно.

Сам алгоритм можно понимать, как процесс "поджигания" графа: на нулевом шаге поджигаем только вершину Х. На каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей; то есть за одну итерацию алгоритма происходит расширение "кольца огня" в ширину на единицу (отсюда и название алгоритма).

Более строго это можно представить следующим образом. Создадим очередь, в которую будут помещаться горящие вершины, а также заведём булевский массив used[], в котором для каждой вершины будем отмечать, горит она уже или нет (или иными словами, была ли она посещена).

Изначально в очередь помещается только вершина Х, и used[Х]=true, а для всех остальных вершин used[i]=false. Затем алгоритм представляет собой цикл: пока очередь не пуста, достать из её головы одну вершину, просмотреть все рёбра, исходящие из этой вершины, и если какие-то из просмотренных вершин ещё не горят, то поджечь их и поместить в конец очереди.

В итоге, когда очередь опустеет, обход в ширину обойдёт все достижимые из Х вершины, причём до каждой дойдёт кратчайшим путём.

Для взвешенного графа алгоритм немного усложняется. Вместо булевского массива used[] заведем массив длин путей path[], элементам которого изначально присвоим бесконечность. Длине пути в исходную вершину присвоим 0: path[Х]=0. Для расчета кратчайших путей придется постоянно проверять, можем ли мы попасть в очередную вершину за более короткий путь и, если да, обновлять значение минимального пути и добавлять эту вершину в очередь еще раз, чтобы заново пересчитать минимальные пути.

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

Приступим к реализации.

Граф будем хранить с помощью матрицы смежности (у нас достаточно много ребер).

Фрагмент кода:

int start = 0;
int end = 0;
Console.Write("Введите N=");
int n = Convert.ToInt32(Console.ReadLine());

int[,] graf = new int[n, n];

Console.Write("Введите M=");
int m = Convert.ToInt32(Console.ReadLine());

for (int i = 0; i < m; i++)
{
    Console.Write("Номер города, из которого идет дорога: ");
    start = Convert.ToInt32(Console.ReadLine());
    Console.Write("Номер города, в который идет дорога: ");
    end = Convert.ToInt32(Console.ReadLine());
    Console.Write("Длина дороги: ");
    int size = Convert.ToInt32(Console.ReadLine());
    graf[start, end] = size;
    graf[end, start] = size;
}

Console.Write("Введите X=");
start = Convert.ToInt32(Console.ReadLine());

Console.Write("Введите Y=");
end = Convert.ToInt32(Console.ReadLine());

int[] path = new int[n];
for (int i = 0; i < n; i++)
{
    path[i] = Int32.MaxValue;
}

Queue<int> list = new Queue<int>();
path[start] = 0;
list.Enqueue(start);
while (list.Count > 0)
{
    int u = list.Dequeue();
    for (int i = 0; i < n; i++)
    {
        if (graf[u, i] > 0)
        {
            if (path[u] + graf[u, i] < path[i])
            {
                path[i] = path[u] + graf[u, i];
                list.Enqueue(i);
            }
        }
    }
}

if (path[end] != Int32.MaxValue)
{
    Console.WriteLine("Ответ: "+path[end]); 
}
else
{
    Console.WriteLine("Дороги нет!"); 
}

Задание*: Попробуйте самостоятельно вывести в консоль кратчайший маршрут движения от города Х в город Y (список номеров городов, через которые надо проехать).

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

Итоги занятия.