- PVSM.RU - https://www.pvsm.ru -
В предыдущем посте [1] рассказывалось об обходе графа в глубину. Сегодня я бы хотел рассказать о не менее важном алгоритме теории графов — об обходе в ширину.
В прошлый раз мы уже научились искать какой-нибудь путь сквозь лабиринт. Всех желающих найти кратчайший путь прошу под кат.
Требуется найти путь от одной вершины графа до другой, причем путь должен быть минимальным по количеству ребер.
Интуитивно хочется рассматривать вершины графа в порядке увеличения расстояния от исходной — так, как показано на рисунке.
Разделим все вершины на три множества:
Очевидно, что, как только все вершины черные, работа алгоритма завершена. Будем хранить все серые вершины в очереди и поддерживать следующее свойство: расстояния до всех серых вершин в том порядке, в котором они лежат в очереди, монотонно не убывают.
Достанем первую вершину из очереди (обозначим ее v). Для каждого из ее соседей w возможен один из двух вариантов:
Повторяем до тех пор, пока есть хотя бы одна серая вершина.
Предполагается, что граф хранится в массиве vector<vector<int>> edges, причем edges[v] содержит номера всех вершин, к которым есть ребро от v. Также предполагается, что в глобальной переменной start хранится номер начальной вершины.
void BFS()
{
queue<int> q;
// Инициализация: есть информация про начальную вершину
q.push(start);
d[start] = 0;
// Главный цикл - пока есть серые вершины
while (!q.empty())
{
// Берем первую из них
int v = q.front();
q.pop();
// Пробегаемся по всем ее соседям
for (int i = 0; i < (int)edges[v].size(); ++i)
{
// Если сосед белый
if (mark[edges[v][i]] == 0)
{
// То вычисляем расстояние
d[edges[v][i]] = d[v] + 1;
// И он становится серым
mark[edges[v][i]] = 1;
q.push(edges[v][i]);
}
}
}
}
Рассмотрим любую вершину v, достижимую из начальной. Пусть p[0] = start, p[1], ..., p[k] = v — кратчайший путь из начальной вершины в вершину v. Тогда полученное в результате работы алгоритма значение d[v] = k.
Доказательство:
Для каждого ребра и каждой вершины алгоритм выполняет константное число действий, следовательно, временная сложность — O(V + E).
Максимальное число вершин, одновременно хранящихся в очереди — V, то есть, максимальный объем используемой памяти — O(V).
В этой статье мы нашли кратчайший путь через лабиринт с использованием одного из самых известных алгоритмов теории графов — BFS.
В следующий раз я постараюсь рассмотреть более сложную задачу на базе нашего любимого лабиринта и, на ее примере, рассказать алгоритм Дейкстры.
Автор: alexeykuzmin0
Источник [2]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/47097
Ссылки в тексте:
[1] предыдущем посте: http://habrahabr.ru/post/200074/
[2] Источник: http://habrahabr.ru/post/200252/
Нажмите здесь для печати.