Поиск, обход в глубину и ширину в графе: алгоритм, описание

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

Граф — это  несколько однотипных вершин, которые связаны между собой ребрами. Каждое отдельное ребро соединяет только две вершины; очень редко, когда ребро может соединять одну вершину саму с собой.

Графы бывают:

• неориентированные — в этих графах важно только присутствие связи между вершинами;


• ориентированные — в этих графах важны присутствие и направление связей между вершинами;


• взвешенные — в этих графах важны присутствие, направление и вес связей между вершинами.

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

Задачи для обхода графа в ширину или глубину могут быть следующие:

• поиск кратчайшего пути между какими-то вершинами;


• найти в графе «дерево» с наименьшим суммарным весом ребер;


• раскрасить вершины графа разными цветами, чтобы у смежных вершин не было одинакового цвета;


• поиск пути, проходящего кратчайшим путем по всем вершинам графа;


• и др.

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

Поиск в ширину, он же BSD (Breadth First Search), сначала обрабатывает все вершины, которые смежны со стартовой, а потом только переходит к их потомкам. Характеризуется плавным передвижением исследования «от соседа к соседу», причем один шаг — это посещение одного «соседа». В процессе своей реализации образуется очередь из еще не пройденных вершин. Данный алгоритм будет работать до тех пор, пока не обнаружит искомое значение.

Поиск в ширину происходит при соблюдении следующей последовательности действий:

1. Необходимо определить стартовую вершину, с которой начинать алгоритм поиска в ширину.


2. Обрабатывается стартовая вершина, а после ее обработки она включается в список «посещенных вершин».


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


4. Организовывается непрерывный цикл, по исключению и включению в очередь пройденных и непройденных вершин.

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

Поиск в глубину, он же DFS (Depth First Search), несет в себе идею такого поиска, при котором мы задаем стартовую вершину и направление движения. Поиск будет происходить по этому направлению до самого конца пути, либо пока не найдется искомое значение вершины. Если дойдя до конца пути, искомое значение не найдено, тогда происходит возвращение «назад» до ближайшей точки расхождения путей и выбирается новое направление для обхода в глубину.

Поиск в глубину характеризуется двумя свойствами:

• стек — это структура для запоминания вершин, которые еще не были обработанными;


• список — это структура для запоминания уже посещенных вершин.

Поиск в глубину  происходит по следующей последовательности действий:

1. Задается стартовая вершина.


2. Определяется искомое значение.


3. Задается вероятный путь для поиска нужного значения.


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

Алгоритм поиска в глубину характеризуется своим движением до конца пути.

Поиск в ширину и в глубину: отличия и сходства

Обход графа в ширину и в глубину имеет общие цели, но разные характеристики, вот несколько из них:

1. Поиск в ширину и в глубину — это и есть обход графа.


2. Поиск в глубину — это  поиск по ребрам графа туда-обратно, а поиск в ширину — это плавный «обход по соседям».


3. В DFS главное — стек, а в BFS главное — очередь.


4. Результат алгоритма поиска в глубину — это некий маршрут, который открывается от стартовой вершины и до искомой. А в алгоритме поиска в ширину маршрут не всегда является результатом.


5. DFS является рекурсивным алгоритмом, а BFS — нет.


6. И др.

Заключение

Если подключить к пониманию этих алгоритмов немного фантазии, то можно представить следующее:

1. Поиск в ширину похож по своей структуре на «круги на воде», когда вы бросаете в воду камень и от места удара плавно расходятся водяные круги. Именно таким же образом работает алгоритм обхода графа в ширину — он постепенно  обходит все вершины, которые находятся максимально близко к стартовой вершине.


2. Поиск в глубину по своей структуре похож на мышь в лабиринте. Когда она не знает куда двигаться, а просто бежит. Если столкнулась с преградой и не нашла выход, тогда она возвращается обратно и ищет другой путь, пока не найдет выход из лабиринта.