Теория графов | Поиск в ширину

Упрощенная теория графов

Теория графов | Поиск в ширину

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

Обзор

Поиск в ширину или просто BFS - это фундаментальный алгоритм, который мы используем для исследования ребер и вершин графа, который играет играет ключевую роль во многих реальных приложениях. Он работает со сложностью O (V + E), где O, V и E соответствуют Big O , вершины и ребра соответственно. Этот механизм действует как основной строительный блок многих приложений. Мы можем различать BFS и DFS по тому, как мы на самом деле пересекаем граф. Как следует из названия, BFS посещает ширь перед глубиной. Это основной факт, который их разделяет. BFS можно использовать для одной цели: для поиска кратчайшего пути в неориентированном графе.

Базовый BFS

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

Если мы запустим BFS с узла 1, он сначала посетит своих соседей, то есть 2, 3 и 4. Когда мы закончим с узлом 1, мы в конечном итоге перейдем к следующему узлу. В нашем случае узлы 2, 3 и 4 не имеют соседей, поэтому мы переходим к следующему непосещаемому узлу, то есть узлу 6. Непосредственными соседями узла 6 являются 5, 7 и 8. Как и в предыдущем случае, узлы 5 и 7 не имеет соседей, поэтому мы должны перейти к узлу 8. Игра меняется, узел 8 имеет двух соседей, которые не были посещены, поэтому мы посещаем их и отмечаем как посещенные. Это был очень простой пример, но поверьте мне - такого рода графики существуют только на бумаге.

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

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

Теперь нужно проверить, не остались ли соседи незамеченными, да. Непосредственными соседями 0 являются 9, 7 и 11. Сначала мы отмечаем 0 как посещенный и добавляем всех соседей 0 в очередь.

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

Следующий узел, который нужно посетить, - это 7, поэтому мы учитываем это и добавляем всех его соседей в очередь. Узел 7 имеет трех соседей, то есть 3, 6 и 11. Если мы посмотрим на очередь, 11 уже есть, поэтому мы опускаем ее и добавляем остальные в очередь, как показано ниже.

Мы повторяем этот процесс до тех пор, пока не будут посещены все элементы в очереди. Это общий рабочий процесс BFS.

Использование очереди

Алгоритм BFS использует очередь для отслеживания узлов, которые будут посещены следующим образом. Достигнув узла, мы добавляем все соседние узлы в одну очередь, чтобы посетить их позже.

Структура данных очереди работает точно так же, как настоящая очередь, объекты приходят и добавляются в конец очереди. Объекты, впервые попавшие в очередь, имеют наивысший приоритет. Это означает, что первый элемент, добавленный в очередь, будет обслужен и первым покинет очередь. С очередями связаны две основные операции, а именно: вставка элемента в конец очереди и удаление элемента спереди, первая называется enqueue, а вторая - удалить из очереди.

Псевдокод

# global variables
n = number_of_nodes_in_the_graph
g = adjacency_list
visited = [false] * n
q = Queue()

q.enqueue(initial node)

while q is not empty
   {
     x = q.dequeue();
     if x is not visited:
      {
        visited[x] = true
        neighbors = g[x] 
        for y in neighbors:
            if y is not visited:  
	       q.enqueue(y)
      }
   }

Мы сохраняем общее количество узлов в переменной n. У нас будет список смежности - структура, используемая для хранения графов в памяти, - которая включает в себя все узлы и соответствующие им смежные соединения. Это карта узлов в списки ребер. Мы используем список посещенный, чтобы проверить, посещен ли конкретный узел, который инициализируется n ложными значениями, потому что мы еще не посетили ни один узел. Как мы обсуждали ранее, мы используем очередь q для отслеживания узлов, которые нужно посетить. Мы вставляем или ставим в очередь один произвольный узел в очередь, чтобы инициировать процедуру BFS. Мы удаляем или выводим из очереди элемент, существующий в очереди, мы должны убедиться, что текущий узел еще не посещен. Если нет, мы меняем статус посещения текущего узла на true. Наконец, мы поместим всех ближайших соседей в используемую очередь. Этот процесс будет повторяться до тех пор, пока очередь не станет пустой, т.е. когда будут посещены все узлы.

Что еще умеет BFS

• Одноранговые сети
• Сайты социальных сетей
• Найти путь
• Вывоз мусора
• Вещание в сети

Это краткое описание поиска в ширину. Я надеюсь, что вы все сочтете это полезным.

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