14.3. Поиск в глубину

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

алгоритмов. Некоторые из них обсуждаются в остальных разделах этой главы. Изложение материала в данном разделе базируется на результатах работы [14.19].

14.3.1. ПВГ в неориентированном графе

Вначале рассмотрим ПВГ в неориентированном графе. Мы будем предполагать, что рассматриваемые графы связны. Если граф не связен, то ПВГ выполняется отдельно в каждой компоненте графа. Мы будем также предполагать, что в графе нет петель.

ПВГ в неориентированном графе выполняется следующим образом:

В графе G выбираем произвольную вершину, например v, и начинаем из нее поиск. Начальная вершина v, называемая корнем ПВГ, после этого считается пройденной.

Затем выбираем ребро инцидентное вершине v, и проходим его, чтобы попасть в вершину w. Ориентируем при этом ребро из v в w. Ребро после этих действий считается просмотренным и называется ребром дерева. Вершина v называется отцом вершины w и обозначается как FATHER (да).

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

1. Если все ребра, инцидентные уже просмотрены, то мы возвращаемся к отцу и продолжаем поиск из FATHER Вершина с этого момента называется полностью сканированной.

2. Если существуют непросмотренные ребра, инцидентные то мы выбираем одно из таких ребер и ориентируем его из в у. Ребро с этого момента считается просмотренным. Необходимо рассмотреть два случая:

Случай 1. Если у ранее не была пройдена, то мы проходим ребро вершину у и продолжаем поиск из вершины у. В этом случае ребро называется ребром дерева и FATHER (у).

Случай 2. Если у ранее была пройдена, то мы продолжаем поиск другого непросмотренного ребра, инцидентного . В этом случае ребро называется обратным ребром. Во время поиска в глубину, когда вершину проходят в первый раз, ей сопоставляется такое целое число что равно i, если является по порядку прохождения вершиной. называется глубиной Ясно, что глубина указывает порядок, в котором проходят вершины при поиске в глубину.

ПВГ завершается, когда мы возвращаемся в корень и все вершины графа пройдены.

Из описания видно, что поиск в глубину разбивает ребра графа G на ребра дерева и обратные ребра. Легко показать, что ребра дерева образуют остов графа G. ПВГ вводит ориентацию на ребра графа G. Получаемый в результате ориентированный граф мы будем

Рис. 14.12. ПВГ в неориентированном графе.

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

В качестве примера на рис. 14.12 показан ПВГ в неориентированном графе. На этом рисунке ребра дерева изображены сплошными, а обратные ребра — штриховыми линиями. Для каждой вершины приведен список инцидентных ей ребер. Такой список для вершины v называется списком смежности вершины v и определяет порядок, в котором ребра, инцидентные вершине у, выбираются для просмотра.

Представим формальное описание алгоритма ПВГ. При этом рассматриваемый граф не обязательно должен быть связным.

Массив MARK, используемый в алгоритме, имеет по одному элементу для каждой вершины. Сначала мы устанавливаем для всех вершин графа, указывая тем самым, что ни одна вершина еще не пройдена. Когда вершина проходится, мы устанавливаем-соответствующий элемент массива MARK равным 1. Массивы DFN и FATHER определены ранее. TREE и BACK — два множества, хранящие ребра дерева и обратные ребра соответственно по мере их выделения.

Алгоритм 14.4. ПВГ в неориентированном графе.

S1. G — данный граф. Пусть Для каждой вершины v графа G установить FATHER

S2. (Начало ПВГ в компоненте графа G). Выбрать какую-либо вершину, например вершину , для которой Положить (Вершина называется корнем рассматриваемой компоненты.)

S3. Если все ребра, инцидентные вершине v, уже помечены как «просмотренные», то идти к шагу — полностью сканирована). Иначе выбрать ребро которое еще не помечено как «просмотренное», и идти к шагу

Ориентировать ребро от с к и пометить его как «просмотренное». Выполнить следующие действия и идти к шагу

1. Если то положить

2. Если то положить

Если FATHER (т. e. v — не корень рассматриваемой компоненты), то положить и идти к шагу Иначе идти к шагу

Если для всех вершин то идти к шагу иначе положить и идти к шагу S2.

S7. (ПВГ завершен) HALT.

Пусть Т — дерево ПВГ связного неориентированного графа. Как мы упоминали ранее, Т — ориентированный остов графа G. Для дальнейшего обсуждения нам необходимо ввести некоторые термины.

Если в дереве Т существует ориентированный путь из вершины v в вершину w, то v называют предком — потомком v. Более того, если то v называется собственным предком w, a — собственным потомком v. Если — ориентированное ребро Т, то v — отец w, сын v. Отметим, что вершина может иметь более одного сына. Вершина v и все ее потомки формируют поддерево дерева Т с вершиной v в качестве корня этого поддерева.

Две вершины и и w являются соотносимыми, если одна из них — потомок другой. Иначе v и w являются несоотносимыми. Если несоотносимы и , то мы будем говорить, что v находится слева от w, иначе v находится справа от w. Ребра графа G, связывающие несоотносимые вершины, называются пересекающими ребрами.

Покажем сейчас, что в графе G не существует пересекающих ребер.

Пусть какие-либо несоотносимые вершины дерева Т. Тогда ясно, что существуют такие две вершины что потомки s, и соответственно (рис. 14.13).

Пусть — поддеревья дерева Т с корнями соответственно. Не нарушая общности, предположим, что

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

Рис. 14.13.

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

Теорема 14.6. Если — ребро в связном неориентированном графе G, то в любом дереве ПВГ этого графа либо v — потомок , либо наоборот.

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

14.3.2. ПВГ в ориентированном графе

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

Случай 1. Вершина w еще не пройдена.

В этом случае — ребро дерева.

Случай 2. Вершина w уже была пройдена.

а. Если w — потомок v в лесе ПВГ (т. е. подграфе на ребрах дерева), то ребро называется прямым ребром.

б. Если w — предок у в лесе ПВГ, то ребро называется обратным ребром.

в. Если v и w несоотносимы в лесе ПВГ и , то ребро является пересекающим ребром. Отметим, что не

существует пересекающих ребер типа где Доказательство этого утверждения проводится аналогично доказательству теоремы 14.6. Сделаем несколько замечаний:

1. Ребро при является либо ребром дерева, либо прямым ребром. Во время поиска различить ребро дерева и прямое ребро довольно просто, так как ребро дерева всегда ведет к новой вершине.

2. Ребро при является либо обратным, либо пересекающим ребром. Такое ребро является обратным ребром, если w еще не полностью сканирована в тот момент, когда встречается ребро при просмотре ребер, исходящих из у.

3. Лес ПВГ (подграф на ребрах дерева) может быть несвязным, даже если рассматриваемый ориентированный граф связен. Первую вершину, проходимую в каждой компоненте леса ПВГ, будем называть корнем соответствующей компоненты. Представим описание алгоритма ПВГ для ориентированного графа. В этом алгоритме мы используем новый массив SCAN, в котором для каждой вершины графа присутствует только один элемент. Вначале мы полагаем SCAN для каждой вершины v, тем самым указывая, что ни одна из вершин полностью не сканирована. Как только вершина полностью сканируется, соответствующий элемент в массиве SCAN полагается равным единице. Как отмечалось ранее, когда встречается ребро для которого , мы классифицируем его как обратное ребро, если или как пересекающее ребро в противном случае. Кроме того, мы используем два массива FORWARD и CROSS, в которых хранятся прямые и пересекающие ребра соответственно.

Алгоритм 14.5. ПВГ в ориентированном графе.

S1. Пусть G — данный ориентированный граф без петель. Пусть Для каждой вершины у графа G положить MARK (у)=0, FATHER (и)=0 и SCAN (v)=Q.

S2. (Начало ПВГ с нового корня.) Взять произвольную вершину, например , для которой MARK Положить

Если все ребра, исходящие из вершины v, уже помечены как «просмотренные», то SCAN и идти к шагу — полностью сканирована). Иначе выбрать ребро да), которое еще не помечено как «просмотренное», и идти к шагу

Пометить ребро да) как «просмотренное», выполнить действия 1 и 2 и идти к шагу

1) Если то положить

2) В противном случае положить {(и, если если {(и,

Если FATHER (т. е. v — не корень), то положить и идти к шагу Иначе идти к шагу

Если для любой вершины MAR то идти к шагу S7, иначе положить и идти к шагу

(ПВГ завершен.) HALT,

Рис. 14.14. а — ПВГ в ориентированном графе G; б — лес ПВГ для графа О.

На рис. 14.14, а представлен ПВГ в ориентированном графе. Для каждой вершины указана ее глубина. Ребра дерева изображены сплошными, а другие ребра — штриховыми линиями. Лес ПВГ изображен отдельно на рис. 14.14, б. Мы отмечали ранее, что лес ПВГ ориентированного графа не может быть связным, даже если этот граф связен. Это видно на рис. 14.14, б. Тогда возникает задача определения достаточных условий для связности леса ПВГ. Докажем, что лес ПВГ сильно связного графа связен. Фактически мы будем доказывать более общий результат.

Пусть Т — лес ПВГ в ориентированном графе . Пусть где — сильно связная компонента графа G. Рассмотрим две произвольные вершины графа G. Не нарушая общности, предположим, что Так как G, сильно связен, то существует ориентированный путь Р из v в w в графе G. Пусть — вершина пути Р с наименьшей глубиной, и пусть

поддерево дерева Т с корнем Отметим, что только пересекающие и обратные ребра могут выходить из поддерева Так как эти ребра ведут к вершинам, имеющим меньшую глубину, чем то отсюда следует, что по достижении в пути Р вершины из все последующие в пути Р вершины будут также принадлежать в частности w также принадлежит Поэтому она является потомком Так как то из алгоритма ПВГ следует, что v также принадлежит Таким образом, две любые вершины v и w графа G имеют общего предка, который также принадлежит

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

Теорема 14.7. Пусть — сильно связная компонента ориентированного графа . Если Т — лес ПВГ, то подграф порожденный множеством вершин связен.

Следующее утверждение является непосредственным следствием из этой теоремы.

Следствие 14.7.1. Лес ПВГ сильно связного графа связен. Легко показать, что алгоритмы ПВГ 14.4 и 14.5 имеют сложность , где — число вершин, — число ребер графа.