Методы систематического обхода вершин графа

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

Базой для решения многих задач глобального анализа являются так называемые алгоритмы обхода или поиска. Необходимо уметь обходить все вершины графа таким образом, чтобы каждая вершина была отмечена ровно один раз. Обычно такое „путешествие" по графу сопровождается нумерацией вершин графа в том порядке, в котором они отмечаются, а также определенной „маркировкой" ребер (или дуг) графа.

Существуют две основные стратегии таких обходов: поиск в глубину и поиск в ширину. Эти стратегии можно описать так.

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

При условии, что в этом списке существует хотя бы одна неотмеченная вершина, продолжаем „путешествие" из первой такой вершины w, действуя как описано выше — „ныряем" вглубь, т.е. просматриваем вершины списка смежности L[w] вершины w, откладывая анализ других элементов L[v] как возможных продолжений поиска „на потом".

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

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

Заметим, что результат поиска в глубину зависит от порядка вершин в списках смежности, представляющих граф, а также от выбора начальной вершины v₀.

На рис. 5.20 показаны примеры поиска в глубину на неориентированном и ориентированном графах.

Рассмотрим неориентированный граф, изображенный на рис. 5.20,a. Списки смежности вершин графа удобно задать кортежами:

Здесь запись v_i → (v_k,...,v_m) означает, что кортеж (v_k,...,v_m) задает список смежности вершины v_i.

Результаты работы алгоритма с использованием приведенных списков смежности проиллюстрированы графически. При поиске отмечаем вершины, присваивая им номера. При этом каждая новая вершина получает номер, на единицу больший, чем текущая. Вершине vo присвоим номер 1. Номера о остальных вершин, присвоенные им в процессе поиска, приведены на графе. Ребра, по которым из текущей вершины переходим к новой, изображены более толстыми линиями.

Прокомментируем поиск в глубину в ориентированном графе, изображенном на рис. 5.20, б. Пусть списки смежности вершин имеют следующий вид:

v₀ → (v₁, v₃), v₁ → (v₂), v₂ → (),

v₃ → (v₁, v₄), v₄ → (v₂),

v₅ → (v₃, v₆, v₇), v₆ → (), v₇ → ().

„Путешествие" начинается в вершине v₀, и ей присваивается номер 1. Первой в списке смежности вершины v₀ стоит вершина v₁. Даем ей номер 2 и продолжаем поиск из этой вершины. В списке смежности последней только одна вершина v₂. Даем ей номер 3 и, так как ее список смежности пуст, возвращаемся в вершину v₁. В списке смежности вершины v₁ нет других вершин, кроме вершины v₂, уже помеченной номером 3, поэтому возвращаемся в вершину v₀.

Второй элемент списка смежности вершины v₀ — вершина v₃. Эта вершина новая. Помечаем ее номером 4 и переходим к рассмотрению ее списка смежности. Первая в списке смежности вершина v₁ уже получила номер 2. Поэтому переходим в новую вершину v₄ и помечаем ее номером 5. Единственный элемент ее списка смежности, вершина v₂, уже отмечена. Возвращаемся в вершину v₃. Здесь тоже нет никаких „отложенных продолжений", и мы снова оказываемся в стартовой вершине v₀. Все вершины из списка смежности стартовой вершины уже отмечены, т.е. все возможные пути поиска из этой вершины пройдены. Тем не менее в графе остались непосещенные (непронумерованные) вершины. Следующей по исходной нумерации вершин графа является вершина v₅. Продолжим поиск из этой вершины и пометим ее номером 6. Первая вершина ее списка смежности —вершина v₃ — уже отмечена. Посещаем следующую вершину — вершину v₆ — и помечаем ее номером 7. Ее список смежности пуст. Возвращаемся в вершину v₅. Посещаем последнюю неотмеченную вершину из ее списка смежности — вершину v₇ — и помечаем ее номером 8. Поскольку все вершины из списка смежности вершины v₅ отмечены, поиск в глубину закончен.

На рис. 5.20, б более толстыми стрелками изображены дуги, по которым из очередной текущей вершины мы переходили к новой.

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

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

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

Для сравнения возьмем неориентированный и ориентированный графы предыдущего примера и рассмотрим для них поиск в ширину (рис. 5.21).

Для неориентированного графа (см. рис. 5.21, а) поиск из стартовой вершины v₀ будем осуществлять так. Стартовой вершине присвоим номер 1. Затем пронумеруем все вершины из списка смежности стартовой вершины в порядке следования их в списке. При этом вершина v₁ получит номер 2, а вершина v₃ — номер 3. Теперь, когда все вершины из списка смежности вершины v₀ отмечены, перейдем в первую по очереди вершину v₁. В ее списке смежности только одна ранее не отмеченная вершина — v₂. Присвоим ей номер 4 и перейдем в вершину v₃ На этом этапе номер 5 получит вершина v₄, а номер 6 — вершина v₅. Затем перейдем в вершину v₂. Поскольку все вершины из списка смежности вершины v₂ уже отмечены, перейдем в вершину v₄. Здесь также все вершины из списка смежности отмечены, поэтому перейдем в вершину v₅. Просмотрим неотмеченные вершины из ее списка смежности и отметим вершины v₆ и v₇, присваивая им номера 7 и 8 соответственно. Теперь, когда список смежности вершины v₅ обработан полностью, перейдем в вершину v₆. Так как в ее списке смежности нет неотмеченных вершин, перейдем в вершину v₇. Здесь также в списке смежности нет неотмеченных вершин. Все вершины обработаны, и поиск в ширину для графа закончен.

Результаты поиска в ширину из вершины v₀ в ориентированном графе представлены на рис. 5.21, б.

Обратим внимание на то, что нумерация вершин при поиске в ширину отличается от нумерации вершин при поиске в глубину. Так, в ориентированном графе на рис. 5.21, б мы сразу отмечаем оба элемента списка смежности вершины v₀. Поэтому вершине, получившей при поиске в глубину номер 4, при поиске в ширину присваивается номер 3.

Перейдем теперь к подробному описанию алгоритмов поиска в глубину и поиска в ширину.

Рассмотрим алгоритм поиска в глубину в неориентированном графе. Будем считать, что граф задан списками смежности, собранными в массив лидеров.

При поиске вершины графа нумеруются в порядке их посещения. Номер вершины v графа, присваиваемый ей при поиске в глубину, обозначим D[v] и будем называть D-номером.

В процессе обхода будем находить фундаментальные циклы графа. Понятие фундаментального цикла в неориентированном графе вводится следующим образом. Пусть в неориентированном графе G = (V, Е) произвольно фиксирован максимальный остовный лес (см. теорему 5.3). Для связного графа это будет максимальное остовное дерево. Множество его ребер обозначим Т. Все ребра из Т назовем древесными, а ребра исходного графа G, не принадлежащие Т, — обратными. Таким образом, фиксируя в графе G максимальный остовный лес, мы тем самым фиксируем разбиение множества его ребер на подмножества древесных и обратных ребер. В силу максимальности остовного леса любая пара вершин графа G, принадлежащих одной и той же компоненте связности, соединена цепью, все ребра которой являются древесными. Возьмем теперь произвольно две вершины u и v, принадлежащие одной и той же компоненте связности графа G. Пусть эти вершины соединены обратным ребром. Поскольку они также соединены цепью, содержащей исключительно древесные ребра, то существует цикл, содержащий эти две вершины, в котором будет единственное обратное ребро {u, v}. Любой цикл графа G, содержащий только одно обратное ребро, назовем фундаментальным.

Докажем, что не существует двух различных фундаментальных циклов, содержащих одно и то же обратное ребро (рис. 5.22). Действительно, если предположить противное, то возникает цикл С, содержащий лишь древесные ребра, что невозможно.

Итак, фиксируя в графе максимальный остовный лес, мы тем самым фиксируем взаимно однозначное соответствие между множеством обратных ребер и множеством фундаментальных циклов.

Одним из способов построения максимального остовного леса может служить поиск в глубину. Именно при поиске в глубину всякое ребро, по которому из текущей вершины мы попадаем в неотмеченную ранее вершину, будет древесным. Каждое ребро, не являющееся древесным, будет обратным. Максимальный остовный лес, находимый с помощью алгоритма поиска в глубину, называют остовным лесом поиска в глубину или глубинным остовным лесом.

Заметим, что классификация ребер зависит от хода работы алгоритма, который определяется стартовой вершиной и расположением вершин в списках смежности.

Таким образом, алгоритм поиска в глубину в неориентированном графе может быть использован для вычисления множества фундаментальных циклов графа, т.е. решения одной из задач глобального анализа.

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

Для организации работы алгоритма поиска в глубину используется способ хранения данных, называемый стеком. Элементы в стеке упорядочиваются в порядке поступления. В стек можно добавлять новые элементы и из него можно извлекать элементы. При этом доступен только последний добавленный элемент — вершина стека, чем и определяется режим работы стека (последним пришел — первым ушел). Образно стек можно представить в виде стопки тарелок. Из стопки можно взять только верхнюю тарелку и только наверх можно добавить новую. Обычно стек реализуется в виде списка.

В алгоритме поиска в глубину используется стек вершин. Мы будем считать, что из стека можно считывать информацию без изменения его содержимого, но в том порядке, в каком ее удаляли бы из стека. Указанная операция считывания понадобится нам для поиска фундаментальных циклов.

Алгоритм поиска в глубину

Вход. Граф G = (V, Е), заданный списками смежности.

Выход. Множества Tree древесных и Back обратных ребер соответственно; множество F_c фундаментальных циклов, массив D, содержащий D-номера вершин.

0. Просмотреть массив лидеров и сформировать множество V₀ вершин графа. Это множество используется для хранения новых (не обработанных алгоритмом) вершин. В ходе работы алгоритма обработанные вершины будут удаляться из этого множества.

В процессе работы алгоритма для каждой вершины v необходимо знать, какие вершины из ее списка смежности L[v] обработаны на предыдущих шагах работы алгоритма. Для этого формируется массив L_p размера |V₀|, в котором хранятся номера первых еще не обработанных алгоритмом вершин списка смежности L[v] каждой вершины v. Первоначально все элементы массива L_p полагают равными 1.

Стек вершин STACK и список вершин фундаментального цикла Cycle положить пустыми (STACK = ∅, Cycle = ∅).

Множества Tree древесных ребер, Back обратных ребер и F_c фундаментальных циклов положить пустыми (Tree = ∅, Back = ∅, F_c = ∅). Массив D-номеров D обнулить.

Задать начальную вершину для поиска (v = v₀). (Обычно это первая вершина массива лидеров.) Счетчик D-номеров вершин count положить равным 1 (count = 1).

1. Если множество V₀ не пусто (V₀ ≠ ∅), перейти на шаг 2, если иначе — на шаг 8 (выход).
2. Если стек пуст (STACK = ∅) и алгоритм стартует из вершины v₀ (count = 1), то перейти на шаг 3, если иначе, то выбрать из множества V₀ произвольную вершину, из которой поиск в глубину будет продолжен (v = u, u ∈ V₀), и перейти на шаг 3.
3. Поместить текущую вершину v в стек STACK. Присвоить вершине v D-номер (D[v] = count). Увеличить счетчик D-номеров на 1 (count = count +1). Удалить вершину v из множества V₀ новых вершин. Перейти на шаг 4.
4. Проверить по элементу L_p[v], что не достигнут конец списка смежности L[v] текущей вершины v. Если в списке смежности есть еще не обработанные вершины, получить из списка смежности очередную вершину w, увеличить L_p[v] на 1 и перейти на шаг 6.
   Если список смежности L[v] вершины v обработан полностью, удалить вершину v из стека STACK и перейти на шаг 5.
5. Если стек STACK пуст, вернуться на шаг 1, если иначе, то в качестве текущей вершины v взять вершину, находящуюся в вершине стека, и перейти на шаг 4.
6. Если вершина w новая (w ∈ V₀), то добавить ребро {v, w} в множество древесных ребер
   (Tree = Tree ∪ {{v,w}}),
   сделать вершину w текущей (v = w) и вернуться на шаг 3.
   Если вершина w не новая (w ∉ V₀), то перейти на шаг 7.
7. Если ребра {v, w} нет среди древесных ({v, w} ∉ Tree), поместить ребро в список обратных ребер
   (Back = Back ∪ {{v, w}}).
   Поместить вершину w в список Cycle. Читать содержимое стека STACK, начиная с вершины стека, до появления вершины w и помещать в список Cycle (включая вершину w), т.е. формировать фундаментальный цикл, соответствующий обратному ребру {v, w}.
   Добавить список Cycle в множество фундаментальных циклов F_c
   (F₀ = F₀ U {Cycle}).
   Список Cycle положить пустым (Cycle = ∅).
   Вернуться на шаг 4.
8. Закончить работу.

Пусть для неориентированного графа, изображенного на рис. 5.20, а, списки смежности имеют вид (5.1). При выполнении поиска в глубину выделенные ребра являются древесными, остальные — обратными. Около каждой вершины указан присвоенный ей D-номер. Фундаментальные циклы — в порядке их нахождения — таковы: v₁, v₂, v₄, v₃, v₁ и v₀, v₁, v₂, v₄, v₃, v₀.

Поиск в глубину в неориентированном графе можно использовать и для нахождения числа его компонент. Очевидно, что это число равно числу опустошений стека от начала до конца поиска в глубину. Регистрируя удаляемые из стека вершины, можно после очередного его опустошения распечатать номера вершин, принадлежащих данной компоненте.

В ориентированном графе поиск в глубину реализуется во многом аналогично поиску в глубину в неориентированном графе. В этом случае возникает остовный ориентированный лес поиска в глубину, дуги которого — это в точности те дуги, по которым в процессе работы алгоритма переходят от очередной вершины к новой, еще не отмеченной вершине. Можно показать, что это максимальный остовный лес исходного графа.

Слабыми компонентами этого глубинного остовного леса будут некоторые ориентированные деревья: поэтому, используемая далее терминология из теории деревьев относится к той или иной слабой компоненте глубинного остовного леса. В ориентированном графе вершинам также присваиваются D-номера. Но классификация дуг при поиске в глубину в ориентированном графе сложнее по сравнению с аналогичной классификацией ребер при поиске в глубину в неориентированном графе.

Различают четыре класса дуг:

1. древесные дуги — каждая такая дуга ведет от отца к сыну в глубинном остовном лесу;
2. прямые дуги — каждая такая дуга ведет от подлинного предка к подлинному потомку (но не от отца к сыну) в глубинном остовном лесу;
3. обратные дуги — от потомков к предкам (включая все петли);
4. поперечные дуги — все дуги, не являющиеся ни древесными, ни прямыми, ни обратными.

Следовательно, в результате работы алгоритма будут получены множества Tree — древесных дуг, Back — обратных дуг, Forward — прямых дуг, С — поперечных дуг и массив D, содержащий D-номера вершин.

В процессе работы алгоритма по сравнению с алгоритмом поиска в глубину в неориентированном графе имеется ряд особенностей. Так, если очередная вершина w, извлеченная из списка смежности текущей вершины v, новая, т.е. w ∈ V₀, то дуга (v, w) является древесной. Следует добавить дугу (v, w) в множество древесных дуг (Tree = Tree ∪ {(v, w)}), сделать вершину w текущей (v = w) и начать ее обработку.

Если вершина w не новая (w ∉ V₀), то дуга (v, w) будет либо прямой, либо обратной, либо поперечной.

Если D-номер вершины v строго меньше D-номера вершины w (D[v] < D[w]), то дуга (v, w) является прямой. Добавляем ее в множество прямых дуг Forward (Forward = Forward ∪ {(v, w)}).

Если D-номер вершины v не меньше D-номера вершины w(D[v] ≥ D[w]), необходимо проверить, есть ли в стеке STACK вершина w. Если вершина w находится в стеке, то дуга (v, w) является обратной и ее следует добавить в множество обратных дуг Back (Back = Back ∪ {(v, w)}). Если вершины w в стеке нет, то дуга является поперечной. Тогда нужно добавить ее в множество поперечных дуг С (С = C ∪ {(v, w)}). Далее следует перейти к рассмотрению очередной вершины из списка смежности текущей вершины (если он не пуст).

Если стек пуст, но не все вершины ориентированного графа обработаны, поиск продолжают из любой необработанной вершины.

В случае ориентированного графа поиск контуров на базе поиска в глубину существенно сложнее, чем в случае неориентированного графа, и здесь он не рассматривается. Однако можно доказать следующий критерии бесконтурности ориентированного графа: ориентированный граф является бесконтурным тогда и только тогда, когда при поиске в глубину от некоторой начальной вершины множество обратных дуг оказывается пустым.

Заметим также, что для ориентированного графа нет такой простой связи между числом опустошений стека и числом компонент, как для неориентированного графа.

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

Можно показать, что алгоритм поиска в глубину имеет сложность порядка mах(|V|,|E|).

Пример 5.7. Проведем поиск в глубину на ориентированном графе, представленом на рис. 5.24. Поиск начнем из вершины vq. Пусть списки смежности вершин имеют следующий вид:

Результаты выполнения поиска в глубину представлены на рисунке: около каждой вершины указан ее D-номер, все весные дуги выделены более толстыми стрелками, а прямые, обратные и поперечные помечены буквами F, B, С соответственно.

Первое опустошение стека происходит после обработки первых пяти вершин (в порядке обхода): v₀, v₂, v₄, v₃, v₁.

После опустошения поиск продолжается из вершины v₇, которой присваивается D-номер 6. (Напомним, что в приведенном выше алгоритме после опустошения стека для продолжения поиска выбирается любая из необработанных вершин.) #

В отличие от алгоритма поиска в глубину, алгоритм поиска в ширину использует не стек, а очередь вершин. Мы дадим здесь вариант поиска в ширину, когда, начиная поиск в неко- некоторой начальной вершине v₀, мы останавливаемся при первом же опустошении очереди. Это значит, что некоторые из вершин могут остаться неотмеченными. Таким образом может быть решена задача распознавания достижимости от заданной вершины. Мы совместим также поиск в ширину с вычислением длины кратчайшего пути от v₀ до любой вершины графа. Будем предполагать, что вершины графа пронумерованы без пропусков числами от 0 до N: V = {v_i:i = 0,N}.

Поиск в ширину рассматриваем только для ориентированного графа.

Алгоритм поиска в ширину в ориентированном графе

Вход. Граф G = (V, Е), заданный списками смежности; v₀ — начальная вершина (не обязательно первый элемент массива лидеров).

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

0. Очередь Q положить пустой (Q = ∅). Все вершины пометить как недостижимые из вершины v₀, присваивая элементам массива М значение +∞ (М[v_i] = +∞, i = 1,N).

Стартовую вершину v₀ пометить номером 0, т.е. длину пути от стартовой вершины v₀ до самой себя положить равной 0 (M[v₀] = 0). Поместить вершину v₀ в очередь Q. Перейти на шаг 1.

1. Если очередь Q не пуста (Q ≠ ∅), то из „головы" очереди извлечь (с удалением из очереди) вершину u и перейти на шаг 2. Если очередь пуста, перейти на шаг 3.
2. Если список смежности L(u) вершины u пуст, вернуться на шаг 1.
   Если список смежности L(u) вершины и не пуст, для каждой вершины w из списка смежности, где M[w] = +∞, т.е. вершины, которую еще не посещали, положить длину пути из стартовой вершины v₀ до вершины w равной длине пути от v₀ до вершины и плюс одна дуга (М[w] = М[u]+1), т.е. отметить вершину w и поместить ее в очередь Q. После просмотра всех вершин списка смежности L(u) вернуться на шаг 1.
3. Распечатать массив М. Закончить работу.

Алгоритм поиска в ширину может быть дополнен процедурой „обратного хода", определяющей номера вершин, лежащих на кратчайшем пути из вершины v₀ в данную вершину u. Для этого необходимо завести массив PR размера |V|, каждый элемент PR[w] которого содержит номер той вершины, из которой был осуществлен переход в вершину w при ее пометке.

Если вершина w находится в списке смежности L(u) вершины u, заполнение элемента массива PR[w] происходит при изменении метки вершины w M[w] с +∞ на единицу. При этом в элементе PR[w] сохраняется номер вершины u (PR[w] = u). Для начальной вершины PR[v₀] можно положить равным 0, в предположении, что начальная вершина v₀ имеет номер 0 и остальные вершины пронумерованы от 1 до N.

Сложность рассмотренного алгоритма поиска в ширину, известного под названием „Алгоритм волнового фронта", составляет O(max(|V|, |E|)).

Пример 5.8. На рис. 5.25 дан пример работы алгоритма волнового фронта (при поиске из вершины v₀) для ориентированного графа, изображенного на рис. 5.24. Списки смежности ориентированного графа имеют вид (5.2).

Около каждой вершины v_i поставлена метка M[v_i], которую получает вершина при поиске в ширину. Выделены дуги, составляющие кратчайшие пути из вершины v₀ в остальные. Отметим, что вершины v₅, v₆, и v₇ не достижимы из v₀ и их начальные метки +∞ остались без изменения. При рассмотренном ходе алгоритма массив PR будет содержать следующие номера вершин: PR[v₀] = 0, PR[v₁] = 0, PR[v₂] = 0, PR[v₃] = 0, PR[v₄] = 2. Для остальных вершин соответствующие значения не определены, поскольку они не „посещались".

Используя массив PR, восстановим кратчайший путь из вершины v₀ в вершину v₄. Поскольку PR[v₄] = 2, a PR[v₂] = 0, искомый путь есть v₀, v₀, v₄.