Алгоритмы на графах. 2

 

ВВЕДЕНИЕ

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

1 ОСНОВЫ ТЕОРИИ ГРАФОВ

 

 

1.1 Ориентированные и неориентированные графы

 

Графом G=(X, U) будем называть совокупность двух конечных множеств: множества вершин X={x₁,…, x_n} и множества ребер (дуг)

U = {u₁…..u_m}, состоящего из некоторых пар элементов (x_i, x_j) множества X.

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

Если пары вершин (x_i, x_j) в множестве U являются неупорядоченными (т.е., порядок соединения вершин несущественен), то граф называется неориентированным (неорграфом), а пары (x_i, x_j) – ребрами этого графа (рис. 1, а). При этом вершины x_i, x_j называют концами (концевыми вершинами) ребра. В данном случае также говорят, что ребро (х_i, x_j,) соединяет вершины x_i и x_j. Если пары вершин (x_i, x_j) в множестве U являются упорядоченными (т.е., порядок соединения вершин существенен), то граф называется ориентированным (орграфом), а пары (x_i, x_j) – дугами. Дуги орграфа, в отличие от ребер неорграфа, будем обозначать < x_i, x_j >. При этом x_i – начало (начальная вершина) дуги, x_j – конец (конечная вершина) дуги. Говорят также, что дуга < x_i, x_j > исходит из вершины x_i и заходит в вершину x_j. Заметим, что < x_i, x_j > и < x_i, x_j > – это различные дуги в графе. При изображении орграфа дуги обозначают стрелками, указывающими их ориентацию (направление). Графы, в которых имеются и неориентированные ребра, и дуги, называются смешанными. Заметим, что любой неориентированный граф может быть представлен в виде орграфа путем замены каждого его ребра двумя противоположно направленными дугами.

В дальнейшем вершины графа  будем обозначать символами х₁, х₂,…, ребра – символами u₁, u₂,… (или парами (x_i, x_j)), дуги – символами u₁, u₂,… (или упорядоченными парами < x_i, x_j >). Число вершин графа обозначим через n, число ребер (дуг) – через m.

Пара вершин x_i, x_j может соединяться двумя или более ребрами (дугами одного направления). Такие ребра (дуги) называют кратными. Количество одинаковых ребер (x_i, x_j) (дуг < x_i, x_j >) называется кратностью соответствующего ребра (дуги). Петлей называется дуга (ребро) с совпадающими начальной и конечной вершинами.

Граф с петлями и  кратными ребрами (дугами) называется псевдографом. Граф с кратными ребрами (дугами) и без петель называется мультиграфом.

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

Так, граф, представленный на рис. 1, а является псевдографом, так как содержит петлю (x_i, x_j) и кратное ребро (х₂, x₃); граф на рис. 1, б является мультиграфом, граф на рис. 1, в-простым графом.

Две вершины графа x_i и х_j называются смежными, если существует соединяющее их ребро (дуга). Два ребра (дуги) смежные, если они имеют общую вершину. Вели ребро (дута) U_k соединяет вершины x_i и x_j. то говорят, что ребро (дуга) инциндентно вершинам x_i и x_j, а вершины x_i и x_j инциндентны ребру (дуге) U_k. Так, на рисунке 1 а вершина x₅ инциндетна ребрам U₆, U₉, U₅, ребра U₁₀ и U₆ являются смежными; смежными являются вершины х₁ и х₆, x₅ и х₆

 

Рисунок 1.1 – Изображения графов

 

Часто граф задают парой (Х, Г), где X – множество вершин графа, а Г – отображение, ставящее в соответствие каждой вершине графа подмножество множества X. При этом для орграфа Г(х_i) – множество вершин x_j є X, для которых в графе существует дуга <х_i, х_j>; Г^-1(х_i) – множество вершин х_k є Х, для которых в графе существует дуга <x_k, x_i>. Для неорграфа Г (х,)= Г^-1(х_i) и означает количество вершин, смежных с вершиной x_i.

Подграфом графа G=(X, U) называется граф G’=(X’.U’), для которого X’є X, U’ є U. Остовным подграфом графа G=(X, U) называется граф G₀= (X, U₀), содержащий все вершины графа G. Порожденным подграфом графа G=(X.H) на множестве вершин Х_р называется граф G_p=(X_p, U_p), где Х_p є Х, а U_p - множество ребер (дуг) графа G, оба конца которых принадлежат множеству Х_р. Так. на рис. 2, а представлен граф G, на рис. 2, б – его произвольный подграф, на рис. 2, в-порожденный подграф графа G на множестве вершин Х {x₁, x₂, x₃, x₄} на рисунке 2, г – один из остовных подграфов графа G.

 

 

Рисунок 1.2 – Изображение остовного подграфа

 

Граф G =(X, U) называется дополнением простого графа G=(X, U), если множества вершин G и G совпадают, а две вершины смежны в G тогда и только тогда, когда они не смежны в G. На рисунке 3 представлен граф G и его дополнение.

 

Рисунок 1.3 – Изображение графа и его дополнения

 

Число дуг, исходящих из вершины  х_i, ориентирован но го графа, называется полустепенью исхода вершины х_i, и обозначается р^-(х,). Число дуг, заходящих в вершин x_i, напивается полустепенью захода вершины x_i и обозначается р⁺(х,). В случае ориентированного псевдографа вклад каждой петли, инциндентной некоторой вершине х_i, равен 1 как в р^-(x_i), так и в р⁺(x_i). Так. для орграфа, представленного на рис. 3, 6 p^-(x₁)=l; p⁺(x₁)=2; р^-(x₂)=3; р⁺(х₂)=2. Для любого орграфа выполняется равенство:

 

 (1.1)

 

В неориентированном графе  число ребер, инциндентных данной вершине  x_i, называется степенью (валентностью) вершины х_i и обозначается р(х_i). Вершина графа, имеющая степень 0, называется изолированной, а вершина, имеющая степень I – висячей. Для неориентированного псевдографа вклад каждой петли, инциндентной вершине x_i, в р(х_i) равен 2. Для неорграфа на рис. 3, а р(х₄)=4; p(x₁)=5. Число вершин нечетной степени в любом графе четно. Для любого неорграфа справедливо следующее равенство

 

(1.2)

 

1.2 Матричный способ задания графов. Изоморфизм и геоморфизм

 

Матрицей смежности неориентированного графа G=(X, U) с n вершинами называется квадратная матрица А порядка n, элементы которой определяются следующим образом:

Для ориентированного графа:

                             (1.3)

 

                                                     (1.4)

 

В псевдографе a_ij =k, где k – кратность ребра (x_i, x_j) (дуги < x_i, x_j >). Петлям в матрице смежности соответствуют элементы, расположенные на главной диагонали. Сумма – элементов матрицы А неорграфа G пo i – и строке (или по i – му столбцу) равна р(х_i). Для орграфа сумма элементов матрицы А по i – й строке равна р^-(х_i). по i – му столбцу р⁺(х_i). Очевидно, что матрица смежности неорграфа является симметричной относительно главной диагонали, Матрицей инциндентности неориентированного графа G=(X, U) с n вершинами и m ребрами называется матрица В размера n x m, элементы которой определяются следующим образом:

 

                     (1.5)

 

Для ориентированного графа:

 

              (1.6)

 

Изоморфизм и геоморфизм.

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

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

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

 

1.3 Маршруты, цепи, циклы в графах

 

Последовательность ребер  неорграфа (x₁, x₂), …, (x_r-1, x_r), в которой конец каждого предыдущего ребра совпадает с началом следующего, называется маршрутом, соединяющим вершины x₁ и x_г. Аналогом маршрута для орграфа является ориентированный маршрут из х₁ в х_г. представляющий собой последовательность дуг, в которой конец предыдущей дуги совпадает с началом следующей. При этом x₁ и x_r называются начальной и конечной вершинами маршрута. Если любые две вершины графа соединены маршрутом, то граф называется связным.

          Маршрут является замкнутым, если начальная вершина совпадает с конечной, и незамкнутым в противном случае. Незамкнутый маршрут, в котором все ребра различны, называют цепью. Незамкнутый ориентированный маршрут, содержащий попарно различные дуги называется путем. Цепь (путь), в которой (в котором) все вершины попарно различны, называется простой (простым). Замкнутая цепь называется циклом, замкнутая простая цепь – простым циклом. Замкнутый путь называется контурам, замкнутый простой путь – простым контурам. Граф, не содержащий циклов, называют ациклическим.

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

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

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

Основные типы графов.

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

          Граф, у которого все вершины имеют одинаковую степень k, называется регулярным (однородным) графом степени k. Число ребер m такого графа определяется следующим образом:

 

  (1.7)

 

Граф, не имеющий ребер, называется пустым, а его вершины – изолированными. Пустой граф, имеющий n вершин, обозначается О_n.

Граф называется полным, если все его вершины смежны. Полный граф порядка n обозначается К_n. Число ребер полною графа К_n определяется следующим образом:

 

  (1.8)

 

Граф G=(X, U) называется двудольным, если существует такое разбиение множества его вершин X на два непересекающихся подмножества X₁ и X₂, что каждое ребро имеет одну концевую вершину в подмножестве X₁, а другую – в надмножестве X₂. Подмножества X₁ и X₂ в данном случае называются долями. Если две вершины графа, входящие в разные доли, смежны, то граф называется полным двудольным и обозначается К_n1,n2, где n₁=|X₁|, n₂=|X₂|. Аналогично определяются k-дольный и полный k-дольный графы (k>2). Граф является двудольным тогда и только тогда, когда он не имеет простых циклон нечетной длины.

Реберным (смежностным) графом простого графа G=(X, U) называется граф L(G)=(U, V), вершинам которою соответствуют ребра графа G, причем все вершины u_i и u_j графа L(G) смежны тогда и только тогда, когда смежны соответствующие им ребра u_i и u_j графа G.

Достижимость и связность.

Вершина x_j неорграфа (орграфа) достижима из вершины x_j, если существуем маршрут, соединяющий х_i и х_j (путь из х_i в х_j). Если в орграфе существуют пути из х_i в х_j и обратно, то говорят, что вершины х_i и х_j взаимно достижимы.

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

Компонентой связности неорграфа называется его максимальный связный подграф, то есть подграф, не содержащийся ни в каком другом связном подграфе этого графа. Аналогично сильной компонентой орграфа называется его максимальный сильно связный подграф.

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

Числом вершинной связности  δ(G) графа называется наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу. Числом реберной связности δ(G) называется наименьшее число ребер, при удалении которых граф становится несвязным. δ^*(G) < δ^*(G) < p^*(G), где p^*(G) – минимальная степень вершин графа.

Вершина х_i называется точкой сочленения (или разделяющей вершиной), если после ее удаления граф становится не связным. Ребро графа называется мостом, если его удаление приводит к несвязному графу.

 

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

 

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

Базой для решения многих задач глобального анализа являются так называемые алгоритмы обхода или поиска.

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

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

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

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

Если же неотмеченных вершин в L[v]   нет, то возвращаемся из  v

в ту  вершину, из которой  мы в нее попали, и продолжаем анализировать  список смежности  этой вершин.

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

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

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

Пример поиска в глубину  на неориентированном и ориентированном  графах:

 

 

 

 

 

 

 

Рисунок 1.4 – Пример поиска в глубину на ориентированном и неориентированном графах

 

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

v0→(v1, v3),    v1→(v2),     v2→( ),

 

v3→(v1, v4),    v4→(v2),

 

v5→(v3, v6, v7),    v6→( ), v7→( ).

 

«Путешествие» начинается в  вершине  v0,  и ей присваивается номер 1.  Первой в списке смежности вершины v0  стоит вершина v1.

Даем ей номер 2 и продолжаем поиск из этой вершины. В списке смежности  последней только одна вершина  v2.  Даем ей номер 3 и, так как ее список смежности пуст, возвращаемся в вершину v1.

В списке смежности вершины  v1, нет других вершин, кроме вершины v1, нет других вершин, кроме вершины v2, уже помеченной номером 3, поэтому возвращаемся в вершину v0.

Второй элемент списка смежности вершины  v0  - вершина v3.

Это вершина новая. Помечаем ее номером  4  и  переходим к  рассмотрению ее списка смежности. Первая в списке смежности вершина  v1  уже получила номер 2. Поэтому переходим в новую вершину v4  и помечаем ее номером 5. Единственный элемент ее списка смежности, вершина v2, уже отмечена. Возвращаемся в вершину v3. Здесь тоже нет никаких «отложенных продолжений»,

И мы снова оказываемся  в  стартовой   вершине  v0. Все вершины из списка смежности стартовой вершины уже отмечены, т.е. все возможные пути поиска из этой  вершины пройдены. Тем не менее в графе остались непосещенные (непронумерованные) вершины. Следующей по исходной нумерации вершин графа является вершина  v5. Продолжим поиск из этой вершины и пометим ее номером 6. Первая вершина ее списка смежности – вершина v3 –уже отмечена. Посещаем следующую вершину – вершину v6 – и помечаем ее номером 7. Ее список смежности пуст. Возвращаемся в вершину v5. Посещаем последнюю неотмеченную вершину из ее списка смежности – вершину v7  - и помечаем ее номером 8. Поскольку все вершины из списка смежности вершины v5  отмечены, поиск в глубину закончен.

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

Рассмотрим теперь поиск  в ширину. При поиске в ширину «правила игры» такие: достигнув  некоторой вершины v , отмечаем ее. Затем просматриваем ее список смежности L[v]  и отмечаем все ранее не отмеченные вершины списка ( при старте поиска  v =v0 ).

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

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

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

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

Для неориентированного графа  поиск из стартовой вершины  v0

будем осуществлять так. Стартовой  вершине присвоим номер 1. Затем пронумеруем  все вершины из списка смежности  стартовой вершины в порядке  следования их в списке. При этом вершина  v1 получит номер 2, а вершина  v3    - номер 3.  Теперь, когда все вершины из списка смежности вершины v0  отмечены, перейдем в первую по очереди вершину v1 . В ее списке смежности только одна ранее не отмеченная вершина - v2 . Присвоим ей номер 4  и перейдем в вершину v3 . На  этом этапе номер 5 получит вершина v4,  , а номер 6  - вершина v5 . Затем перейдем в вершину v2. Поскольку все вершины из списка смежности вершины v2  уже отмечены, перейдем в вершину v4 . Здесь также все вершины из списка смежности отмечены, поэтому перейдем в вершину v5. Просмотрим неотмеченные  вершины из ее списка смежности и отметим вершины v6  и v7, присваивая им номера 7  и 8  соответственно. Теперь, когда список смежности вершины   v5  обработан полностью, перейдем в вершину v6. Так как в ее списке смежности нет неотмеченных вершин, перейдем в вершину  v7. Здесь также в списке смежности нет неотмеченных вершин. Все вершины обработаны, и поиск в ширину для графа закончен.

 

 

 

 

 

 

 

 

 

Рисунок 1.5 -  Результаты поиска в ширину из вершины v0 в ориентированном графе

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

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

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

Слабыми компонентами этого  глубинного остовного леса будут  некоторые ориентированные деревья: поэтому, используемая далее терминология из теории деревьев относится к той  или иной слабой компоненте глубинного остовного леса.

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

 D-номером. 

Классификация дуг при  поиске в глубину в ориентированном  графе сложнее по сравнению с  аналогичной классификацией ребер  при поиске в глубину в неориентированном  графе.

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

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

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

вершин.

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

Если вершина w не новая (w V0), то дуга (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 в стеке нет, то дуга является поперечной. Тогда нужно добавить ее множество поперечных дуг С ( С = С {(v,w)} ). Далее следует перейти к рассмотрению очередной вершины из списка смежности текущей вершины (если он не пуст).

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

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

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

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

Пример:

Проведем поиск в глубину на ориентированном графе, представленном на рисунке.

 

Рисунок 1.6 - Поиск в глубину на ориентированном графе

 

Поиск начнем из вершины  v0. Пусть списки смежности вершин имеют следующий вид:

 

    v0→( v2, v3, v1),    v1→( v3),     v2→( v4, v3),

    v3→( v4),    v4→( v1),   v5→( v1),

    v6→( v3, v5),    v7→( v5, v6).

 

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

Первое опустошение стека  происходит после обработки первых пяти вершин (в порядке обхода):  v0, v2, v4, v3, v1.

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