My deep learning

Алгоритмы поиска в ширину и в глубину

Теги: algorithms  bfs  dfs  graphs 

Поиск в ширину и поиск в глубину представляют две основных парадигмы обхода графов.

Поиск в ширину (breadth-first search, BFS)

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

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

BFS

Алгоритм реализуется на основе очереди FIFO (First In, First Out – «Первым пришёл — первым ушёл»), с помощью которого отслеживаются ноды, которые алгоритм уже посещал. Очередь позволяет добавлять объекты в конец списка и удалять объекты из начала за постоянное время.

BFS алгоритм

Вход: граф \(G = (V, E)\), где \(V\) это множество нод, а \(E\) множество ребер. Стартовая вершина \(s \in V\).

Выход граф \(G_{explored} = (V, E)\), при условии, что каждая вершина такого графа достижима из s тогда и только тогда, когда она размечена алгоритмом как «разведанная».

  1. пометить s как разведанную вершину, все остальные как неразведанные
  2. определить очередь \(Q\), инициализированную вершиной s
  3. до тех пор, пока очередь \(Q\) непустая:
  4.   удалить вершину из начала очереди \(Q\), обозначив ее как v
  5.   для каждого ребра \((v, w)\) в списке смежности v:
  6.     если w не разведана:
  7.       пометить w как разведанную
  8.       добавить w в конец \(Q\)

BFS используется для поиска кратчайшего пути и связных компонент в графе.

Поиск в глубину (depth-first search, DFS)

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

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

DFS DFS DFS DFS

DFS реализуется на основе стека LIFO (last in, first out, «последним пришёл — первым ушёл»).

DFS алгоритм

Вход: граф \(G = (V, E)\), где \(V\) это множество нод, а \(E\) множество ребер. Стартовая вершина \(s \in V\).

Выход граф \(G_{explored} = (V, E)\), при условии, что каждая вершина такого графа достижима из s тогда и только тогда, когда она размечена алгоритмом как «разведанная».

  1. пометить s как разведанную вершину, все остальные как неразведанные
  2. определить стек \(S\), инициализированную вершиной s
  3. до тех пор, пока стек \(S\) непустой:
  4.   удалить вершину сверху стека \(S\), обозначив ее как v
  5.   если v не разведана:
  6.     пометить v как разведанную
  7.     для каждого ребра \((v, w)\) в списке смежности v:
  8.       добавить w наверх стека \(S\)

Кроме того, алгоритм может быть реализован рекурсивно.

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

Свойства алгоритмаов DFS и DFS

  • вершина размечается как разведанная тогда и только тогда, когда существует путь из s в v в графе \(G\)
  • время работы алгоритма \(O(m + n)\), где \(m = \vert E \vert\), а \(n = \vert V \vert\) (для представления графа в виде списков смежности. Для матрицы смежности сложность составит \(O(n^2)\))

Поделиться статьей

Все статьи с тегом algorithms

Этот проект поддерживается KonstantinKlepikov