ЗАДАНИЕ 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
Вершина и |
Стек 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.

Рис. 5.3
Таблица 5.2
Вершина |
и |
Очередь Q |
ПШ-номер |
Метка |
|
Г |
1 |
2,3,5 |
2' |
2 |
3,5,4 |
3' |
3 |
5,4 |
4' |
5 |
4, 6,7 |
5' |
4 |
6,7 |
6' |
6 |
7 |
Т |
7 |
0 |