ЗАДАНИЕ 5 Базовые задачи и алгоритмы на графах

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

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

Среди различных методов систематического обхода всех вершин графа наиболее известны поиск в глубину и поиск в ширину [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

Рис. 5.2

При поиске в ширину для s = 1 вершины будут проходиться в следующем порядке: 1,2, 3, 5, 4, 6, 7. На рис. 5.3 и в табл. 5.2 указаны результаты этого обхода: ПШ-номера (номера по порядку поиска в ширину) вершин; метки вершин; текущее состояние очереди Q.

Рис. 5.3

Таблица 5.2