Доказательство. Обходы графа по глубине и ширине

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

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

При поиске в глубину, отправляясь в «путешествие» по гра­фу из некоторой начальной вершины 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) связен, то поиск в ширину и глубину обойдут все вершины по одному разу.

1. Единственность обхода вершин. Обходятся только вершины попавшие в Т. В Т попадают только неотмеченные вершины. При попадании в Т вершина отмечается. Следовательно, любая вершина будет обойдена не более одного раза.

2. Завершаем ость алгоритма. Всего в Т может попасть не более р вершин. На каждом шаге одна вершина удаляется из Т. Следовательно, алгоритм завершит работу не более чем через р шагов.

3. Обход всех вершин. От противного. Пусть алгоритм закончил работу, и вершина z не обойдена. Значит, w не попала в Т. Следовательно, она не была отмечена. Отсюда следует, что все вершины, смежные с z, не были обойдены и отмечены. Аналогично, любые вершины, смежные с неотмеченными, сами не отмечены (после завершения алгоритма). Но G связан, значит, существует путь (x, z). Следовательно, вершина x не отмечена. Но она была отмечена на первом шаге.

Рассмотрим более подробно алгоритм поиска в ширину в графе.

Вход. Граф G =(X, V), заданный матрицей смежности - начальная вершина (не обязательно первый элемент массива).

Выход. Массив Т меток вершин, где каждая метка равна длине пути от x ₀ до x.

Шаг 1.В начале все вершины у нас не отмечены w [ x ]=0.

Шаг 2. Выбираем вершину с которой начнем обход и помещаем ее в структуру данных Т.

Шаг 3. Отмечаем эту вершину в качестве пройденной w [ x ]=1.

Шаг 4. Начинаем просматривать смежные с ней вершины, если данную вершину не просматривали (т.е. w [ z ]=0) то помещаем ее в структуру данных Т, и отмечаем ее как пройденную w [ z ]=1.

Шаг 5. Обход будем выполнять до тех пор, пока не отметим все вершины.

На рис. 4.37 представлен граф, вершины которого занумерованы согласно очередности, в которой они посещаются в процессе поиска в ширину.

Рис. 4.37

Дата добавления: 2014-12-27