что такое поиск в ширину
Обход графа: поиск в глубину и поиск в ширину простыми словами на примере JavaScript
Доброго времени суток.
Что такое обход графа?
Простыми словами, обход графа — это переход от одной его вершины к другой в поисках свойств связей этих вершин. Связи (линии, соединяющие вершины) называются направлениями, путями, гранями или ребрами графа. Вершины графа также именуются узлами.
Двумя основными алгоритмами обхода графа являются поиск в глубину (Depth-First Search, DFS) и поиск в ширину (Breadth-First Search, BFS).
Несмотря на то, что оба алгоритма используются для обхода графа, они имеют некоторые отличия. Начнем с DFS.
Поиск в глубину
DFS следует концепции «погружайся глубже, головой вперед» («go deep, head first»). Идея заключается в том, что мы двигаемся от начальной вершины (точки, места) в определенном направлении (по определенному пути) до тех пор, пока не достигнем конца пути или пункта назначения (искомой вершины). Если мы достигли конца пути, но он не является пунктом назначения, то мы возвращаемся назад (к точке разветвления или расхождения путей) и идем по другому маршруту.
Давайте рассмотрим пример. Предположим, что у нас есть ориентированный граф, который выглядит так:
Мы находимся в точке «s» и нам нужно найти вершину «t». Применяя DFS, мы исследуем один из возможных путей, двигаемся по нему до конца и, если не обнаружили t, возвращаемся и исследуем другой путь. Вот как выглядит процесс:
Здесь мы двигаемся по пути (p1) к ближайшей вершине и видим, что это не конец пути. Поэтому мы переходим к следующей вершине.
Мы достигли конца p1, но не нашли t, поэтому возвращаемся в s и двигаемся по второму пути.
Достигнув ближайшей к точке «s» вершины пути «p2» мы видим три возможных направления для дальнейшего движения. Поскольку вершину, венчающую первое направление, мы уже посещали, то двигаемся по второму.
Мы вновь достигли конца пути, но не нашли t, поэтому возвращаемся назад. Следуем по третьему пути и, наконец, достигаем искомой вершины «t».
Так работает DFS. Двигаемся по определенному пути до конца. Если конец пути — это искомая вершина, мы закончили. Если нет, возвращаемся назад и двигаемся по другому пути до тех пор, пока не исследуем все варианты.
Мы следуем этому алгоритму применительно к каждой посещенной вершине.
Необходимость многократного повторения процедуры указывает на необходимость использования рекурсии для реализации алгоритма.
Заметка: этот специальный DFS-алгоритм позволяет проверить, возможно ли добраться из одного места в другое. DFS может использоваться в разных целях. От этих целей зависит то, как будет выглядеть сам алгоритм. Тем не менее, общая концепция выглядит именно так.
Анализ DFS
Давайте проанализируем этот алгоритм. Поскольку мы обходим каждого «соседа» каждого узла, игнорируя тех, которых посещали ранее, мы имеем время выполнения, равное O(V + E).
Краткое объяснение того, что означает V+E:
V — общее количество вершин. E — общее количество граней (ребер).
Может показаться, что правильнее использовать V*E, однако давайте подумаем, что означает V*E.
V*E означает, что применительно к каждой вершине, мы должны исследовать все грани графа безотносительно принадлежности этих граней конкретной вершине.
С другой стороны, V+E означает, что для каждой вершины мы оцениваем лишь примыкающие к ней грани. Возвращаясь к примеру, каждая вершина имеет определенное количество граней и, в худшем случае, мы обойдем все вершины (O(V)) и исследуем все грани (O(E)). Мы имеем V вершин и E граней, поэтому получаем V+E.
Далее, поскольку мы используем рекурсию для обхода каждой вершины, это означает, что используется стек (бесконечная рекурсия приводит к ошибке переполнения стека). Поэтому пространственная сложность составляет O(V).
Теперь рассмотрим BFS.
Поиск в ширину
BFS следует концепции «расширяйся, поднимаясь на высоту птичьего полета» («go wide, bird’s eye-view»). Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. Это означает следующее:
Вместо следования по пути, BFS подразумевает посещение ближайших к s соседей за одно действие (шаг), затем посещение соседей соседей и так до тех пор, пока не будет обнаружено t.
Чем DFS отличается от BFS? Мне нравится думать, что DFS идет напролом, а BFS не торопится, а изучает все в пределах одного шага.
Далее возникает вопрос: как узнать, каких соседей следует посетить первыми?
Для этого мы можем воспользоваться концепцией «первым вошел, первым вышел» (first-in-first-out, FIFO) из очереди (queue). Мы помещаем в очередь сначала ближайшую к нам вершину, затем ее непосещенных соседей, и продолжаем этот процесс, пока очередь не опустеет или пока мы не найдем искомую вершину.
Анализ BFS
Может показаться, что BFS работает медленнее. Однако если внимательно присмотреться к визуализациям, можно увидеть, что они имеют одинаковое время выполнения.
Очередь предполагает обработку каждой вершины перед достижением пункта назначения. Это означает, что, в худшем случае, BFS исследует все вершины и грани.
Несмотря на то, что BFS может казаться медленнее, на самом деле он быстрее, поскольку при работе с большими графами обнаруживается, что DFS тратит много времени на следование по путям, которые в конечном счете оказываются ложными. BFS часто используется для нахождения кратчайшего пути между двумя вершинами.
Таким образом, время выполнения BFS также составляет O(V + E), а поскольку мы используем очередь, вмещающую все вершины, его пространственная сложность составляет O(V).
Аналогии из реальной жизни
Если приводить аналогии из реальной жизни, то вот как я представляю себе работу DFS и BFS.
Когда я думаю о DFS, то представляю себе мышь в лабиринте в поисках еды. Для того, чтобы попасть к цели мышь вынуждена много раз упираться в тупик, возвращаться и двигаться по другому пути, и так до тех пор, пока она не найдет выход из лабиринта или еду.
Упрощенная версия выглядит так:
В свою очередь, когда я думаю о BFS, то представляю себе круги на воде. Падение камня в воду приводит к распространению возмущения (кругов) во всех направлениях от центра.
Упрощенная версия выглядит так:
Выводы
Поиск в ширину
Поиск в ширину (англ. breadth-first search) — один из основных алгоритмов на графах, позволяющий находить все кратчайшие пути от заданной вершины и решать многие другие задачи.
Поиск в ширину также называют обходом — так же, как поиск в глубину и все другие обходы, он посещает все вершины графа по одному разу, только в другом порядке: по увеличению расстояния до начальной вершины.
Описание алгоритма
Реализация
Обратим внимание, что путь выведется в обратном порядке.
В неявных графах
Поиск в ширину часто применяется для поиска кратчайшего пути в неявно заданных графах.
Поиск в ширину можно использовать для нахождения выхода из лабиринта
Такой подход будет работать за оптимальное линейное время, однако с точки зрения реализации проще адаптировать не входные данные, а сам алгоритм обхода в глубину:
Перед запуском bfs следует убедиться, что не произойдет выход за пределы границ. Вместо того, чтобы добавлять проверки на _x = n и т. п. при просмотре возможных соседей, удобно сделать следующий трюк: изначально создать матрицу a с размерностями на 2 больше, чем нужно, и на этапе чтения данных заполнять её в индексации не с нуля, а с единицы. Тогда границы матрицы всегда будут заполнены нулями (то есть помечены непроходимыми) и алгоритм никогда в них не зайдет.
Применения и обобщения
Помимо нахождения расстояний в невзвешенном графе, обход в ширину можно использовать для многих задач, в которых работает обход в глубину, например для поиска компонент связности или проверки на двудольность.
Множественный BFS. Добавив в очередь изначально не одну, а несколько вершин, мы найдем для каждой вершины кратчайшее расстояние до одной из них.
Это полезно для задач, в которых нужно моделировать пожар, наводнение, извержение вулкана или подобные явления, в которых источник «волны» не один. Также так можно чуть быстрее находить кратчайший путь для конкретной пары вершин, запустив параллельно два обхода от каждой и остановив в тот момент, когда они встретятся.
Игры. С помощью BFS можно найти решение какой-либо задачи / игры за наименьшее число ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа.
В качестве (нетривиального) примера: собрать кубик Рубика за наименьшее число ходов.
Кратчайшие циклы. Чтобы найти кратчайший цикл в ориентированном невзвешенном графе, можно произвести поиск в ширину из каждой вершины. Как только в процессе обхода мы пытаемся пойти из текущей вершины по какому-то ребру в уже посещённую вершину, то это означает, что мы нашли кратчайший цикл для данной вершины, и останавливаем обход. Среди всех таких найденных циклов (по одному от каждого запуска обхода) выбираем кратчайший.
Аналогично можно найти все вершины на каком-либо кратчайшем пути.
0-1 BFS. Если веса некоторых ребер могут быть нулевыми, то кратчайшие пути искать не сильно сложнее.
Это можно сделать и напрямую, запустив BFS внутри BFS, однако можно заметить, что достаточно при посещении вершины просто добавлять всех её непосещенных соседей по нулевым ребрам в голову очереди, чтобы обработать их раньше, чем те, которые там уже есть. Это легко сделать, если очередь заменить деком:
Также вместо дека можно завести две очереди: одну для нулевых ребер, а другую для единичных, в внутри цикла while сначала просматривать первую, а только потом, когда она станет пустой, вторую. Этот подход уже можно обобщить.
Заметим, что алгоритм также работает когда есть общее ограничение на длину пути, а не только на вес каждого ребра. Для более общего случая, когда веса ребер могут быть любыми неотрицательными, есть алгоритм Дейкстры, который мы разберем в следующей статье.
Алгоритм поиска в ширину на графе
Речь пойдет, как вы уже наверное догадались, о графах, а именно о алгоритме обхода графа в ширину.
Чтобы проникнуться в суть графов, попробуйте решить следующую, довольно известную задачу:
Река, огибающая остров, делится на два рукава, через которые переброшены 7 мостов (см. рисунок ниже). Спрашивается, можно ли совершить такую прогулку, чтобы за один раз перейти все эти мосты, не переходя ни через один мост два или более раз? 
Суть алгоритма поиска в ширину в том, что мы обходим связный граф таким образом, что сначала мы рассматриваем родителя, потом по очереди рассматриваем его предков, потом рассматриваем предков его предков и т.д.(см. рисунок ниже)
Порядок обхода вершин графа.
Можно объяснить алгоритм двумя способами:
Первой вершине (родителю всех остальных вершин) приписываем метку 1. Рассматриваем все смежные с ней вершины и приписываем им метку 2. Дальше рассматриваем окружение вершин с меткой 2 и присваиваем метку 3 всем вершинам, кроме самой главной (родителя всех вершин).
Второй способ объяснения (по моему более понятнее, ну по крайней мере писать его легче) подразумевает под собой имитирование «горения» графа. Т.е. мы поджигаем самую первую вершину, дальше огонь перекидывается на смежные с ней вершины, с них на смежные с ними и т.д. Со смыслом я думаю мы разобрались, однако для меня основной проблемой стала реализация алгоритма. (Программист я не очень то начитанный, поэтому не вините меня).
Скажу сразу, что для реализации данного алгоритма нужны знания: циклов, массивов и очередей. С последним у меня как раз возникли проблемы, т.к. такую структуру данных я, до написания этого алгоритма, не встречал.
Ну напишу я пока что примерную реализацию на С++:
Поясню немного.
Данный код совершает обход по связному графу в ширину. Предполагается, что нам известны данные о смежности вершин ( которые хранятся в матрице смежности matrix[] ) Если вершины i и j смежные, то matrix[i][j]=1 Ну вроде бы все. Профессиональные кодеры, пожалуйста, не ругайтесь за такое кривое объяснение и ещё более кривой код (но я частенько нуждаюсь в кривых, но довольно простых кодах).
Поиск в ширину (BFS) на С#
Сразу скажу, что статья больше подойдёт людям, желающим познакомиться с поиском в ширину, и новичкам, осваивающим программирование. К тому же, когда мне понадобился этот метод, я нигде не нашёл наглядного рабочего примера на C#.
Устно об алгоритме:
Разберём алгоритм на произвольном графе (для простоты примера рёбра не имеют вес).
Последовательность алгоритма заключается в следующим:
1. Выбирается произвольно вершина графа (отмечается серым).
2.Последовательно рассматриваются вершины (так же отмечаются серым), связанные с нашей первой вершиной (после этого она становится не серой, а чёрной).
3. Выполняется пункт 2 для отмеченных (серых) вершин до тех пор, пока все вершины не будут закрашены чёрным.
Теперь тоже самое, но более техническим языком:
1. Выбирается произвольная вершина в графе и помещается в очередь.
2. В очередь помещаются все вершины графа смежные с уже находящейся в очереди вершиной, после чего эта вершина выталкивается из очереди.
3. Выполняется пункт 2 для всех вершин, находящихся в очереди.
Теперь перейдём непосредственно к коду (C#):
В качестве графа мы будем использовать массив, программировать будем на консоли (для примера достаточно будет и её). К слову, в примере будем использовать ориентированный граф.
Зададим начальные переменные и заполним наш массив.
g — это массив массивов, где первый индекс определяет нашу вершину с которой мы работаем, а второй массив определяет индексы вершин, с которыми наша вершина связана и не связана (если значение равно 0 — не связана, следовательно, если 1 — связана). То есть, например g[1][5] = 0, означает, что от первой к пятой вершины нет связи (но так как граф ориентированный, то матрица смежности будет не симметричной, следовательно если g[1][5] = 0, то это не означает что и g[5][1] = 0).
used — логический массив, в который мы будем заносить посещённые вершины.
Идём далее, собственно, сам алгоритм в действии:
while — будет выполняться до тех пор, пока очередь не опустеет. В начале каждой итерации присваиваем переменной u значение выталкиваемого элемента очереди.
for — цикл, проходящий по всем вершинам. В нём для начала проверяем нашу вершину на наличие у неё смежных вершин, если есть и если такая вершина не добавлена в массив посещённых вершин (массив used), то мы её туда добавляем, а так же добавляем в нашу очередь.
Собственно вот он весь алгоритм. Да, пожалуй далеко без изысков, и можно сделать куда лучше, но пишу статью исключительно для ознакомительных целей, надеясь, что кому-то, кто так же, как когда-то и я, искал наглядные примеры, она поможет.
Вот примерно как должна получиться программа:
От обхода в ширину к алгоритму Дейкстры
Вместо введения
Разбирал свои старые, так сказать, «заметки», и наткнулся на эту. У меня же еще нет инвайта на хабре, подумал я, и решил опубликовать. В этой статье я расскажу, как разобраться в алгоритме Дейкстры поиска кратчайших путей из данной вершины в графе. При чем я приду к нему естественным образом от алгоритма обхода графа в ширину.
В комментариях попросили рассказать подробнее о структуре данных, скрывающейся за priority_queue в STL C++. В конце статьи приводится краткий рассказ и ее реализация.
Обход графа в ширину
Первый алгоритм, который хотелось бы описать, и который однозначно нельзя пропустить — это обход графа в ширину. Что же это такое? Давайте немного отойдем от формального описания графов, и представим себе такую картину. Выложим на земле веревки, пропитанные чем-нибудь горючим, одинаковой длины так, чтобы ни одна из них не пересекалась, но некоторые из них касались концами друг с другом. А теперь подожжем один из концов. Как будет вести себя огонь? Он равномерно будет перекидываться по веревкам на соседние пересечения, пока не загорится все. Нетрудно обобщить эту картину и на трехмерное пространство. Именно так в жизни будет выглядеть обход графа в ширину. Теперь опишем более формально. Пусть мы начали обход в ширину из какой-то вершины V. В следующий момент времени мы будем просматривать соседей вершины V (соседом вершины V назовем вершины, имеющий общее ребро с V). И так до тех пор, пока все вершины в графе не будут просмотрены.
Реализация обхода в ширину
Пусть мы находимся в какой-то вершине в процессе обхода в ширину, тогда воспользуемся очередью, в которую будем добавлять всех соседей вершины, исключая те, в которых мы уже побывали.
В этой реализации g — это список смежных вершин, т.е. в g[u] лежит список смежных вершин с u(в качестве списка использован std::vector), used — это массив, который позволяет понять, в каких вершинах мы уже побывали. Здесь обход в ширину не делает ничего, кроме самого обхода в ширину. Казалось бы, зачем? Однако его можно легко модифицировать для того, чтобы искать то, что нам нужно. Например расстояние и путь от какой-либо вершины до всех остальных. Следует заметить, что ребра не имеют веса, т.е. граф не взвешенный. Приведем реализацию поиска расстояний и путей.
Здесь p — это массив предков, т.е. в p[v] лежит предок вершины v, dist[v] — это расстояние от вершины из которой мы начинали обход, до вершины v. Как восстановить путь? Это сделать довольно легко, просто пройдя по массиву предков нужной нам вершины. Например, рекурсивно:
Кратчайшие пути
Все дальнейшие рассуждения будут верны только если веса ребер не отрицательны.
Теперь перейдем к взвешенным графам, т.е. ребра графа имеют вес. Например длина ребра. Или плата за проход по нему. Или время, которое требуется для прохода по нему. Задача — найти кратчайший путь из одной вершины, в какую-нибудь другую. В этой статье я буду отталкиваться от обхода в ширину, не помню, чтобы видел такой подход где-нибудь еще. Возможно я это пропустил. Итак, давайте посмотрим еще раз на реализацию обхода в ширину, а конкретно на условие добавления в очередь. В обходе в ширину мы добавляем в очередь только те вершины, в которых мы еще не были. Теперь же изменим это условие и будем добавлять те вершины, расстояние до которых можно уменьшить. Очевидно, что очередь опустеет тогда и только тогда, когда не останется ни одной вершины, до которой можно уменьшить расстояние. Процесс уменьшения пути из вершины V, назовем релаксацией вершины V.
Следует заметить, что изначально путь до всех вершин равен бесконечности(за бесконечность возьмем какую-нибудь достаточно большую величину, а именно: такую, что ни один путь не будет иметь длины, большей величины бесконечности). Этот алгоритм напрямую следует из обхода в ширину, и именно до него я дошел сам, когда решал первую в жизни задачу на кратчайшие пути в графе. Стоит упомянуть, что такой способ ищет кратчайший пути от вершины, из которой мы начали алгоритм, до всех остальных. Приведу реализацию:
Почему храним в списке смежности именно такие пары? Чуть позже станет понятно, когда мы усовершенствуем этот алгоритм, но, честно говоря, для данной реализации пары можно хранить и наоборот. Можно немного улучшить добавление в очередь. Для этого стоит завести массив bool, в котором будем помечать, находится ли сейчас вершина, которою нужно прорелаксировать, в очереди.
Если присмотреться, то этот алгоритм очень похож на алгоритм Левита, но все-таки это не он, хотя в худшем случае работает за ту же асимптотику. Давайте грубо оценим это. В худшем случае нам придется проводить релаксацию каждый раз, когда мы проходим по какому-либо ребру. Итого O(n * m). Оценка довольно грубая, но на начальном этапе этого вполне хватит. Стоит так же заметить, что это именно худший случай, а на практике даже такая реализация работает довольно быстро. А теперь, самое интересное!… барабанная дробь… Улучшим наш алгоритм до алгоритма Дейксты!
Алгоритм Дейкстры
Теперь дело осталось за малым, понять как эффективно искать вершину с минимальным расстоянием до нее. Для этого воспользуемся очередью с приоритетами (куча, heap). В stl есть класс, который реализует ее и называется priority_queue. Приведу реализацию, которая, опять же, напрямую следует из предыдущего(описанного в этой статье) алгоритма.
Скорее всего не совсем понятно, что здесь происходит. Начнем с объявления очереди с приоритетами. Здесь первый аргумент шаблона — данные, которые хранятся в очереди, а конкретно пары вида (расстояние до вершины, номер вершины), второй аргумент шаблона — это контейнер, в котором будут храниться данные, третий аргумент, компаратор(находится, кстати, в заголовочном файле functional). Почему нам нужен какой-то другой компаратор? Потому что при стандартном объявлении priority_queue >, доставать получится только те вершины, расстояние до которых максимально, а нам-то нужно совсем наоборот. Асимптотика такого решения поставленной задачи O(n * log(n) + m * log(n)).
Действительно, всего у нас n релаксаций, а вершину с минимальной длиной пути до нее, мы ищем за log(n) (именно такая асимптотика у стандартной очереди с приоритетами stl). Так же следует заметить, что у нас может получится так, что мы добавили в очередь одну и ту же вершину, но с разными путями до нее. Например, мы провели релаксацию из вершины A, у которой в соседях вершина C, а потом провели релаксацию из вершины B, у которой так же в соседях вершина C, для ухода от проблем, связанных с этим, будем просто пропускать те вершины, которые мы достали из очереди, но расстояние из очереди до которых не актуально, т.е. больше, чем текущее кратчайшее. Для этого в реализации присутствует строчка if (u.first > dist[u.second]) continue;.
Вместо заключения
Оказалось, что на самом деле очень легко писать Дейкстру за O(n * log(n) + m * log(n))!
Дополнение
В комментариях попросили рассказать, как можно реализовать своими руками priority_queue.
Пусть перед нами стоит следующая задача (как в алгоритме Дейкстры).
Нужно поддерживать структуру данных, которая удовлетворяет следующим требованиям:
1) Добавление не более, чем за O(log(n)) времени.
2) Удаление минимального элемента не более, чем за O(log(n)) времени.
3) Поиск минимума за O(1) времени.
Оказывается, что этим требованиям удовлетворяет структура данных, которую в русско-язычной литературе обычно называют «куча», в англо-язычной «heap» или «priority queue».
Вообще говоря, куча — это дерево. Давайте рассмотрим свойства этого дерева подробнее. Пусть у нас уже построена куча, тогда определим ее следующим образом — для каждой вершины в куче верно, что элемент в этой вершине не больше, чем элементы в ее потомках. Тогда в корне дерева лежит минимальный элемент, что позволяет нам в дальнейшем искать минимум за O(1).
Теперь доопределим нашу кучу так, чтобы и остальные свойства выполнялись. Назовем уровнем вершины в дереве расстояние от корня до нее. Запретим добавлять новый уровень в куче, до тех пор пока не заполнен целиком предыдущий. Более формально: пусть текущая максимальная высота дерева H, тогда запрещено добавлять вершины на высоту H + 1, пока есть возможность добавить ее на высоту H. Действительно, при таких условиях высота кучи всегда не более, чем O(log(n)).
Осталось научиться добавлять и удалять элементы в кучу.
Реализовывать кучу будем на бинарном дереве, в котором будет не более одной вершины с количеством потомков меньшим двух. Дерево будем хранить в массиве, тогда потомки вершины на позиции pos, будут лежать на позициях 2 * pos и 2 * pos + 1, а родитель будет лежать на позиции pos / 2.
Добавлять элемент будем на первое возможное вакантное место на текущем максимальном уровне, затем выполнять операцию, которая называется «просеивание вверх». Это значит, что пока родитель добавленного элемента больше, чем сам элемент, то поменять позиции добавленного элемента и родителя, повторять рекурсивно до корня. Докажем, что при этом не нарушаются свойства кучи. Это просто, так как текущий элемент меньше, чем родитель, то он так же и меньше, чем все потомки родителя.
Удалять минимальный элемент будем следующим образом: сначала поменяем местами корень дерева с последним элементом на максимальном уровне, затем удалим вершину, в которой был этот элемент (теперь там будет минимум). Свойства кучи после этого нарушатся, а чтобы их восстановить нужно выполнить операцию, которая называется «просеивание вниз». Начинаем от корня рекурсивно: для текущего элемента находим из потомков минимальный, меняем местами с текущим элементом, рекурсивно запускаемся для вершины, с которой поменяли текущий элемент. Заметим, что после этой операции, свойства кучи выполняются.
Так как высота дерева O(log(n)), то добавление и удаление будет работать за O(log(n)).