На протяжении всей этой серии статей мы устанавливали связи между вещами. Мы увидели, как связанные списки лежат в основе стеков и очередей, а деревья - это подмножество графов. Оказывается, все, что кажется сверхсложным - по крайней мере, в мире информатики - не так уж и сложно, как может показаться на первый взгляд. Скорее, все состоит из более мелких мелких вещей.

Осознание этого - большой шаг к демистификации информатики и всего, что с ней связано. Большие, устрашающие идеи - это на самом деле просто мелкие, которые были построены, расширены и реструктурированы для другой цели. Как только мы можем разбить проблему на мельчайшие движущиеся части, эта проблема становится гораздо менее сложной, чтобы попытаться понять (и решить!).

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

Итак, приступим!

Поиск по графику

Если вы чувствуете серьезные случаи дежавю и думаете, что мы уже рассмотрели вопросы поиска в ширину ранее в этой серии, то вы правы! Фактически, мы также рассмотрели поиск в глубину в этой серии! Так почему же это появляется снова, если мы уже являемся экспертами по обоим этим алгоритмам?

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

Итак, обо всем по порядку: что мы имеем в виду, когда говорим «траверс»? Начнем с определения.

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

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

Подобно тому, как это реализовано в древовидных структурах данных, поиск в глубину проходит вглубь структур графа, посещая дочерние узлы перед посещением родственных или соседних - узлы. И при обходе дерева, и при обходе графа алгоритм DFS использует структуру данных стека. Для сравнения: алгоритм поиска в ширину в общих чертах проникает в структуру, посещая соседние узлы-братья перед посещением дочерних узлов. При обходе дерева и графа алгоритм BFS реализует структуру данных очереди.

Мы увидим, что между этими двумя алгоритмами есть довольно много различий в зависимости от того, применяются ли они к древовидной структуре или структуре графа. Но давайте вернемся к нашей задаче: пониманию внутренней работы BFS применительно к графам!

Чтобы понять обход графа BFS, мы рассмотрим один пример: неориентированный граф, который показан здесь.

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

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

Пошаговый обход BFS

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

Основа обхода графа в ширину состоит из следующих основных шагов:

  1. Добавьте узел / вершину из графа в очередь узлов для «посещения».
  2. Посетите самый верхний узел в очереди и отметьте его как таковой.
  3. Если у этого узла есть соседи, проверьте, были ли они «посещены» или нет.
  4. Добавьте в очередь любые соседние узлы, которые еще нужно «посетить».
  5. Удалите узел, который мы посетили, из очереди.

Эти пять шагов непрерывно повторяются для каждого узла в графе, пока у нас не останется больше узлов для проверки в нашей очереди. Конечно, увидеть эти шаги, написанные на бумаге, не так эффективно (или полезно!), Как увидеть пример BFS в действии, поэтому давайте воспользуемся нашим примером графа и проведем по нему поиск в ширину, начиная с узла b в качестве «Родительский» узел нашего поиска.

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

Как только у нас появится элемент (узел b) в нашей очереди, мы «посетим» его и отметим как «посещенный». Процесс посещения узла фактически означает, что мы замечаем его существование, а также проверяем соседние узлы. В этом случае соседними узлами b являются узлы f и a; Итак, мы добавим их в нашу очередь.

После того, как мы посетили узел b и добавили его соседей в очередь, мы можем удалить узел b из очереди, поскольку мы сделали с ним все, что нам нужно. Фактически, мы выводим из очереди узел b и помещаем в очередь узлы f и a. Обратите внимание, что либо узел a, либо f мог быть добавлен первым в очередь; поскольку они оба являются соседями, не имеет значения, в каком порядке они добавлены в очередь, если они добавлены вместе.

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

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

После того, как мы добавили и c, и g (в любом порядке, который мы выберем), мы можем удалить узел f из верхней части очереди, поскольку мы закончили работу по его посещению! Мы видим, что оба узла c и g находятся в двух шагах от «родительского» узла b; другими словами, они находятся на расстоянии двух узлов от узла b, что помещает их на уровне 2 расстояния от основного «родительского» узла.

Далее идет узел a, который находится в начале очереди. Мы знаем, что делать, правда?

Мы добавим его соседние узлы - у него только один, узел e - в конец нашей очереди. Мы отметим узел a как «посещенный», покрасив его в синий цвет, а затем мы сможем удалить его из очереди в начале очереди. Теперь в нашей очереди есть ссылки на вершины c, g и e.

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

Когда мы посмотрим на соседние узлы узла c, мы увидим, что одним из его соседей является узел f. Но мы уже посетили узел f! Точно так же еще один из соседей узла c - это узел g, который уже находится в очереди. Итак, мы знаем, что он уже находится в очереди на посещение, поэтому нам не нужно снова добавлять его в очередь. Остается третий и последний сосед узла c: узел d. Этот узел не был посещен и не был поставлен в очередь, поэтому мы действительно можем сделать что-нибудь с этим соседним узлом. Что ж, если быть более конкретным, мы можем добавить его в очередь.

После того, как мы проверили всех соседей узла c, мы можем удалить его из очереди и продолжить свою жизнь! Мы перейдем к следующему элементу в очереди - узлу g. Аналогичная ситуация и здесь. Его сосед, узел c, уже был посещен, а другой сосед, узел d, только что был поставлен в очередь, поэтому ни с одной из этих двух вершин делать нечего.

Единственный сосед, который требует обработки, - это узел h, который мы добавим в конец нашей очереди. Как только мы это сделаем, мы можем исключить узел g из начала очереди.

Теперь мы заметим, что узел h, который мы только что поставили в очередь, находится на трех уровнях от «родительского» узла; то есть это узел уровня 3, поскольку он находится на расстоянии 3 узлов от нашего начального узла b.

В нашей очереди теперь есть узлы e, d и h. Когда мы «посещаем» узел e, мы видим, что у него есть один сосед, узел a, который уже был посещен. Итак, здесь мы ничего не можем сделать, кроме как пометить e как посещенный и удалить его из очереди.

Аналогичная история для узлов d и h. В обоих случаях каждый из этих двух соседей узла либо 1) уже был посещен, либо 2) уже находится в очереди, ожидая посещения.

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

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

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

Например, узел h является узлом уровня 3 и имеет 3 ребра / указателя, по которым мы можем вернуться к родительскому узлу, узлу b. Также может быть путь от узла h к b, который намного длиннее трех шагов, или может быть несколько трехэтапных «кратчайших путей» от узла h к b. Важно то, что у нас есть по крайней мере один из этих кратчайших путей, легко доступных нам в силу того, что мы проследили назад и нашли при обходе нашего графа BFS.

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

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

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

Сложности поиска в ширину

Изучение такого алгоритма, как поисковый граф в ширину, увлекательно, но не так весело, если не знать, насколько эффективно он будет перемещаться по графу! Лучший способ понять сложность обхода графа BFS во время выполнения - это изучить, как он на самом деле работает с представлением графа, другими словами, исследуя, как алгоритм будет работать на реальном графике, в его программном формат.

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

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

Так, например, вершина e имеет только один соседний узел a. Следовательно, смежный связанный список для вершины e содержит ссылку на индекс 0 в массиве, где находится узел a. Если мы бегло просмотрим этот список смежности, мы увидим, что он отображается непосредственно на тот же график, с которым мы имели дело.

Когда мы реализуем BFS для этого представления графа списка смежности, нам понадобится одна дополнительная структура данных: «посещенный» массив, который мы будем использовать, чтобы отслеживать, какие вершины были посещены (а какие нет). Этот массив будет содержать только FALSE логических значений для запуска. Но когда мы посещаем самый первый узел, мы помечаем его как TRUE, и в конечном итоге весь массив будет заполнен TRUE значениями в конце алгоритма BFS.

Мы можем начать понимать, сколько времени на самом деле требуется для запуска BFS на графе, если мы рассмотрим, как алгоритм будет работать с этим списком смежности.

Например, давайте сделаем первый шаг, добавив узел b в очередь и фактически посетив его; что все это будет включать?

  1. Когда мы выбираем произвольный начальный «родительский» узел для b, мы отмечаем его как посещенный, изменяя его состояние в массиве «посещенных».
  2. Затем, после изменения его значения с FALSE на TRUE в массиве «посещенных», мы помещаем его в очередь.
  3. Затем, при удалении вершины из очереди, нам нужно проверить ее соседние узлы и выполнить итерацию (цикл) по смежному связанному списку. Узел b имеет два соседних узла, расположенных с индексами 0 и 5 соответственно.
  4. Если какой-либо из этих соседних узлов не был посещен (не имеет состояния TRUE в массиве «посещенных»), мы помечаем его как посещенный и помещаем в очередь.
  5. Наконец, мы будем делать это до тех пор, пока не дойдем до NULL (пустого) указателя в связанном списке, прежде чем перейти к следующему узлу в очереди. Когда очередь полностью опустеет, мы знаем, что мы закончили выполнение алгоритма.

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

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

Если мы должны посетить каждый узел один раз и проверить каждое ребро в его списке смежности, сложность выполнения как для ориентированного, так и для неориентированного графа равна сумме вершин и их ребер, представленных графом в его представлении списка смежности, или O ( V + E)

Для неориентированного графа это означает, что мы посещаем все вершины (V), и 2 | E | края. Для ориентированного графа это означает, что мы посещаем все вершины (V) и | E | края. Размер представления графа в виде списка смежности напрямую зависит от того, сколько времени нам потребуется, чтобы пройти через него с помощью поиска в ширину, что делает его линейным алгоритм!

Алгоритм обхода графа BFS является популярным поисковым решением и особенно удобен для быстрого определения кратчайшего пути между двумя точками на графе. Однако меня еще больше интересует странное и несколько печальное происхождение этого алгоритма поиска.

Фактически он был впервые получен немецким инженером по имени Конрад Цузе, который создал первый в мире программируемый компьютер, и его часто называют изобретателем современного компьютера. Цузе впервые теоретизировал алгоритм обхода графа BFS в 1945 году как решение для поиска связанных компонентов или двух связанных вершин структуры данных графа. Он написал об алгоритме BFS в своей докторской диссертации, которая даже не была опубликована до 1972 года. Поворот сюжета в этой истории состоит в том, что, когда Цузе впервые написал о BFS в своей диссертации, его идея была фактически отвергнута !

Алгоритм BFS был позже заново изобретен четырнадцатью годами позже Эдвардом Ф. Муром в 1959 году, американским профессором математики, который (заново) создал алгоритм как решение для поиска кратчайшего пути между двумя точками в лабиринте. Всего несколько лет спустя, в 1961 году, он был независимо обнаружен исследователем по имени C.Y. Ли, который в то время работал в Bell Telephone Labs. В статье Ли Алгоритм соединений путей и его приложения BFS описывается как алгоритм маршрутизации проводов для поиска оптимального пути между двумя точками на компьютере IBM 704.

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

Ресурсы

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

  1. Визуализации обхода графа, VisuAlgo
  2. Поиск в ширину, факультет компьютерных наук, Гарвард
  3. Поиск в ширину (BFS) на графах. Часть 2 - Реализация, Сеш Венугопал
  4. Поиск в ширину (BFS), MIT OpenCourseWare
  5. Обход графа - сначала в ширину, а в глубину, CollegeQuery