Главная Промышленная автоматика.

еще до следующего вызова процедуры d/яи никогда не вызывается для вершин, помеченных этой меткой. Поэтому общее время выполнения строк (2) и (3) для просмотра всех списков смежности пропорционально сумме длин этих списков, т.е. имеет порядок 0(e). Таким образом, предполагая, что е > п, общее время обхода по всем вершинам орграфа имеет порядок 0(e), необходимое для "просмотра" всех дуг графа.

Пример 6.13. Пусть процедура dfs применяется к ориентированному графу, представленному на рис. 6.16, начиная с вершины А. Алгоритм помечает эту вершину как visited и выбирает вершину В из списка смежности вершины yl. Поскольку вершина В помечена как unvisited, обход графа продолжается вызовом процедуры dfs(B). Теперь процедура помечает вершину В как visited И выбирает первую вершину из списка смежности вершины В. В зависимости от порядка представления вершин в списке смежности, следующей рассматриваемой вершиной может быть или вершина С, или вершина D.

Предположим, что в списке смежности вершина С предшествует вершине D. Тогда осуществляется вызов dfs(C). В списке смежности вершины С присутствует только вершинау4, но она уже посещалась ранее. Поскольку все вершины в списке смежности вершины С исчерпаны, то поиск возвращается в вершину В, откуда процесс поиска продолжается вызовом процедуры dfs(D). Вершины А и С из списка смежности вершины D уже посещались ранее, поэтому поиск возвращается сначала в вершину В, а затем в вершину yl.

На этом первоначальный вызов dfs(A) завершен. Но орграф имеет вершины, которые еще не посещались: Е, F и G. Для продолжения обхода вершин графа выполняется вызов dfs(E). □


Рис. 6.16. Ориентированный граф

Глубинный ОСТОВНЫЙ лес

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

В добавление к дугам дерева существуют еще три типа дуг, определяемых в процессе обхода орграфа методом поиска в глубину. Это обратные, прямые и поперечные дуги. Обратные дуги (как дуга С -> А на рис. 6.17) - такие дуги, которые в остов-ном лесе идут от потомков к предкам. Отметим, что дуга из вершины в саму себя также является обратной дугой. Прямыми дугами называются дуги, идущие от предков к истинным потомкам, но которые не являются дугами дерева. На рис. 6.17 прямые дуги отсутствуют.

Дуги, такие как £)-»СиО->2)на рис. 6.17, соединяющие вершины, не являющиеся ни предками, ни потомками друг друга, называются поперечными дугами. Ес-



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


Рис. 6.17. Глубинный остовный лес для орграфа из рис. 6.16

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

dfnumberlv] := count; count ;= count + 1;

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

Всем потомкам вершины v присваиваются глубинные номера, не меньшие, чем номер, присвоенный вершине v. Фактически вершина w будет потомком вершины V тогда и только тогда, когда выполняются неравенства dfnumberiv}< dfnum.ber(wY- dfnumber{v) + количество потомков вершины у. Очевидно, что прямые дуги идут от вершин с низкими номерами к вершинам с более высокими номерами, а обратные дуги - от вершин с высокими номерами к вершинам с более низкими номерами.

Все поперечные дуги таюке идут от верпшн с высокими номерами к вершинам с более низкими номерами. Чтобы показать это, предположим, что есть дуга х -> у и выполняется неравенство dfnum.ber{xY. dfnum.beriy).0iCK)B3. следует, что верпшна х пройдена (посещена) раньше вершины у. Каждая вершина, пройденная в промежуток времени от вызова dfs(x) и до завершения dfs(y), становится потомком вершины X в глубинном остовном лесу. Если при рассмотрении дуги х -*у вершина у еще не посещалась, то эта дуга становится дугой дерею. В противном случае дуга х -* у будет прямой дугой. Таким образом, если для дуги х -у выполняется неравенство dfnumberix)< dfnumberiy),To она не может быть поперечной дугой.

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

Для истинных потомков вершины v первое из приведенных неравенств должно быть строгим. - Прим. ред.



6.6. Ориентированные ациклические графы

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




Рис. 6.18. Три ориентированных графа

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

((а + Ь)*с + ((а + Ь) +е) * (е + /)) * ((а + Ь)*с).

Подвыражения а + Ь w. {а + Ь)*с встречаются в выражении несколько раз, поэтому они представлены верщинами, в которые входят несколько дуг.


Рис. 6.19. Ориентированный ациклический граф для арифметического выражения

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

1. Ни для какого элемента а из множества S не выполняется аНа (свойство антирефлексивности) .

2. Для любых а, Ь, с из S, таких, что aRb и ЬНс, выполняется aRc (свойство транзитивности) .





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 [62] 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0037