Во многих задачах теории графов необходимо обойти некоторый граф, посещая каждую его вершину в точности один раз и выполняя при этом некоторую систематическую обработку информации, относящуюся к этой вершине. К таким задачам относятся: отыскание остовного дерева; распознавание связности, двудольности и ацикличности графа; поиск «узких» мест графа; проверка достижимости вершин и др. Все эти задачи и алгоритмы их решения составляют операционный базис теории графов. Изучение методов систематического перебора вершин графа и практика решения на компьютере базовых задач теории графов - цель данного задания.
Обход вершин графа в глубину или ширину
Среди различных методов систематического обхода всех вершин графа наиболее известны поиск в глубину и поиск в ширину [5, 6, 12-19]. Алгоритмы поиска лежат в основе многих задач на графах.
В алгоритме 5.1, реализующем обход вершин графа в глубину или ширину, предполагается, что граф G = (V,E), где V = {vi, ..., v„}, п > 1, задан списками смежности. Это означает, что для каждой вершины v е V известна ее окрестность N(v). Обход начинается с вершины s е V, которая также должна быть задана.
Алгоритм 5.1. Поиск в глубину или ширину
1. Инициализация. Пусть X- одномерный массив для записи меток вершин графа. Вначале все вершины графа считать неотмеченными: для каждой вершины v е V положить A[v];=0.
2. Начало обхода. Исходную вершину s записать в структуру данных Q и отметить, полагая А[^]:= 1.
3. Посещение вершины. Из Q извлечь вершину и и вывести ее в качестве очередной пройденной вершины.
4. Пополнение Q. Проанализировать каждую вершину со е N(u). Если ЛХсо] = 0, т. е. вершина со еще не отмечена, то записать ее в Q и отметить, полагая .Y[oo]:= 1.
5. Продолжение или завершение обхода. Если Q^0, то перейти к пункту 3. Иначе обход завершить.
Если структура данных Q - стек (удаление и добавление элементов производится с одного конца), то обход вершин графа по алгоритму 5.1 соответствует поиску в глубину. Поиск в глубину называют иногда обходом в вертикальном порядке. Если Q - очередь (удаление элементов производится с одного конца, а добавление - с другого), то обход называется поиском в ширину, или обходом в горизонтальном порядке.
Для связного графа G алгоритм 5.1 обеспечивает обход всех вершин графа, поскольку в Q попадают по порядку все вершины из множества
При этом каждая вершина обходится только один раз. Действительно, посещаются только те вершины, которые попали в Q (пункт 3 алгоритма). В Q записываются только неотмеченные вершины, которые сразу же отмечаются (пункт 4 алгоритма).
Оценим сложность алгоритма 5.1. Каждое включение и исключение вершины из Q выполняется за время 0(1). Поэтому для всей работы, связанной с изменением Q, достаточно времени 0(п), где n = V. Для каждой вершины и е V пункт 4 алгоритма выполняется d(u) = | N(u) | раз. Поэтому затраты на его выполнение в целом можно оценить так:
где т = Е- число ребер графа. Таким образом, временная сложность поиска в глубину или ширину составляет 0(п + т). Заметим, что здесь использовано равенство
справедливое для любого {п, т)-графа G = {V,E) и известное в теории графов как «лемма о рукопожатиях».
Пример 5.1. Рассмотрим (7, 10)-граф G = (V,E), для которого V= {1, 2, 3, 4, 5, 6, 7} (рис. 5.1). При поиске в глубину вершины этого графа будут проходиться в следующем порядке: 1, 5, 7, 6, 4, 3, 2. Обход начинается с вершины s = 1.
Рис. 5.1
На рис. 5.2 и в табл. 5.1 приведены результаты обхода: ПГ- номера (номера по порядку поиска в глубину) вершин; метки (исходные номера) вершин; текущее состояние стека Q.
Таблица 5.1
Вершина и
Стек Q
ПГ-номер
Метка
1*
1
2,3,5
2*
5
2, 3,4, 6, 7
3*
7
2, 3, 4, 6
4*
6
2,3,4
5*
4
2,3
6*
3
2
1*
2
0
Рис. 5.2
При поиске в ширину для s = 1 вершины будут проходиться в следующем порядке: 1,2, 3, 5, 4, 6, 7. На рис. 5.3 и в табл. 5.2 указаны результаты этого обхода: ПШ-номера (номера по порядку поиска в ширину) вершин; метки вершин; текущее состояние очереди Q.
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter 