Обходы графа по глубине и ширине

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

При поиске в глубину, отправляясь в «путешествие» по гра­фу из некоторой начальной вершины x_о, мы действуем следую­щим образом. Пусть, «путешествуя», мы достигли некоторой вершины x (в начале «путешествия» x=x₀). Отмечаем вершину x и просматриваем вершины из ее списка смежности L[x].

При условии, что в этом списке существует хотя бы одна неотмеченная вершина, продолжаем «путешествие» из первой такой вершины y, действуя как описано выше - «ныряем» вглубь, т.е. просматриваем вершины списка смежности L[y] вершины y, откладывая анализ других элементов L[x] как возможных продолжений поиска «на потом».

Если же неотмеченных вершин в L[x] нет, то возвращаемся из x в ту вершину, из которой мы в нее попали, и продолжаем анализировать список смежности этой вершины.

Рассмотрим теперь поиск в ширину. При поиске в ширину «правила игры» такие: достигнув некоторой вершины, от­мечаем ее. Затем просматриваем ее список смежности L[x] и отмечаем все ранее не отмеченные вершины списка (при старте поиска x=x_o). После того как отмечены все вершины из L[x], вершину x считаем полностью обработанной и продолжаем об­работку вершин из списка L[x] по очереди согласно описанным правилам.

Именно в обработке сразу всего списка смежности текущей вершины заключается принципиальное отличие поиска в шири­ну от поиска в глубину: там мы «ныряли» как можно «глубже», а здесь идем, «загребая» сразу все, что можно.

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

Теорема 4.11.2. Если граф G=(X,V) связен, то поиск в ширину и глубину обойдут все вершины по одному разу.