Поиск в ширину и глубину

Поиск в ширину

Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа.

Поиск в ширину выполняется в следующем порядке:

Началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.

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

Поиск в глубину

Поиск в глубину

Поиск в ширину

Поиск в ширину

Поиск в глубину

Поиск в глубину (Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.

Пусть задан граф G = (V,E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

  1. Из множества всех белых вершин выберем любую вершину, обозначим её v1.
  2. Выполняем для неё процедуру DFS(v1).
  3. Перекрашиваем её в чёрный цвет.
  4. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.


Оставить комментарий