Главная Промышленная автоматика. procedure ПОИСКЕ (у): begin 1. пометить узел v как "старый"; 2. ПГНОМЕР[у]СЧЕТ; 3. СЧЕТ -СЧЕТ+ 1; 4. НИЖНИЙ[у] - ПГНОМЕР[у]; 5. for wL[v] do 6. if узел w помечен как "новый" then begin 7. добавить (v, w) к Т; 8. ОТЕДН -у; 9. ПОИСКБИ; 10. if НИЖНИ1[а;] > ПГНОМЕР[у] then обнаружена двусвязная компонента; 11. НИЖНИЙ[у] -МШ(НИЖНИЙ[у], НИЖНИЙМ) end 12. else if ш-не ОТЕЦ[у then 13. НИЖНИ1[у] -МШ(НИЖНИ1:1[у], ПГНОМЕРН) Рис. 5.11. Поиск в глубину с вычислением функции НИЖНИЙ. наем ПОИСКЕ (Уо) (рис. 5. И), чтобы построить глубинное остовное дерево 5=(У, Т) и вычислить НИЖНИЙ[у] для каждого v из V. 2. Когда в строке 5 процедуры ПОИСКЕ выбирается узел w, помещаем ребро (у, w) в СТЕК (т. е. магазинную память для ребер), если оно еще не там Когда в строке 10 обнаруживается пара (у, w), для которой W - сын узла у и НИЖНИЙ йу]>у, выталкиваем из СТЕКа все ребра вплоть до (у, w). Эти ребра образуют двусвяз-ную компоненту графа G. □ Пример 5.6. Остовное дерево с рис. 5.9, построенное поиском в глубину, воспроизведено на рис. 5.12, причем узлы переименованы в соответствии с ПГНОМЕР и указаны значения функции НИЖНИЙ. Например,. ПОИСКЕ(6) устанавливает, что НИЖ-НИЙ[6]=4, так как есть обратное ребро (6, 4). Тогда П0ИСКБ(5), 1) Заметим, что если (у, ш) - ребро, то vLlw] и wL[v]. Поэтому (у, w) встречается дважды: один раз, когда посещается узел с, и второй раз, когда посещается узел w. Узнать, попало ли уже ребро (у, w) в СТЕК, можно, установив, что v<w ч W - «старый» узел или v>w и ш=ОТЕЦ[у]. нижний нижний [2] = 1 (2 нижний [3]=2 (з НИЖНИЙ [4] =4 нижний [5] =41 (slj Jl (( 7 ) НИЖНИЙ [71 = 4 НИЖНИЙ [6] = 4 Рис. 5.12. Остовное дерево с рис. 5.9 со значениями функции НИЖНИЙ. который вызвал П0ИСКБ{6), полагает НИЖНИЙ[5]=4, поскольку 4 меньше начального значения НИЖНИЙ[5], равного 5. Закончив ПОИСКЕ (5), обнаруживаем (строка 10), что НИЖ-НИЙ[51=4. Следовательно, 4 - точка сочленения. В этот момент магазин содержит такие ребра (от дна к вершине): (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 4), (5, 7), (7, 4). Поэтому выталкиваем все ребра вплоть до (4, 5). Таким образом, мы подаем на выход ребра (7, 4), (5, 7), (6, 4), (5, 6) и (4, 5), которые являются ребрами первой найденной двусвязной компоненты. Закончив ПОИСКЕ (2), обнаруживаем, что НИЖНИЙ[2] = 1, и опустошаем магазин, хотя 1 - не точка сочленения. Это гарантирует, что двусвязная компонента, содержащая корень, тоже будет найдена. □ Теорема 5.3. Алгоритм 5.3 правильно находит двусвязные компоненты графа Gee ребрами и тратит на это время 0(e). Доказательство. Для доказательства того, что шаг 1 требует время 0(e), надо просто обобщить аналогичное свойство процедуры ПОИСК (теорема 5.2). Шаг 2 просматривает каждое ребро один раз, помещает его в магазин и впоследствии выталкивает его оттуда. Поэтому сложность шага 2 равна 0(e). Что касается корректности алгоритма, то лемма 5.5 гарантирует, что точки сочленения будут найдены правильно. Даже если корень не является точкой сочленения, алгоритм обращается с ним как с таковой, чтобы выделить двусвязную компоненту, содержащую корень. Мы должны доказать, что если НИЖНИЙ[йу]>1;, то по окончании процедуры ПОИСКЕ (ш) ребра, расположенные в СТЕКе над (V, w), будут в точности ребрами из двусвязной компоненты. содержащей (у, w). Это делается индукцией по числу b двусвязных компонент в G. Базис, т. е. случай Ь=1, тривиален, поскольку тогда V - корень дерева, (у, w) - единственное древесное ребро, выходящее из у, и по окончании процедуры ПОИСКЕ (w) все ребра графа G находятся в СТЕКе. Теперь допустим, что предположение индукции верно для всех графов с b дву связными компонентами, и пусть О-граф с b+l двусвязными компонентами. Пусть ПОИСКЕ (w) - это первый вызов процедуры ПОИСКЕ, по окончании которого НИЖНИЙЫ] >у, где (у, w) - древесное ребро. Так как никакие ребра не были удалены из СТЕКа, то множество ребер в СТЕКе, расположенных выше (у, w), состоит из всех ребер, инцидентных потомкам узла w. Легко показать, что эти ребра в точности совпадают с ребрами той двусвязной компоненты, куда входит (у, w). Удалив их из СТЕКа, алгоритм ведет себя так, как он вел бы себя на графе G, получаемом из G, если удалить двусвязную компоненту, содержащую ребро (у, w). Осталось только сделать шаг индукции, поскольку G состоит из b двусвязных компонент. □ 5.4. ПОИСК В ГЛУБИНУ В ОРИЕНТИРОВАННОМ ГРАФЕ Алгоритм 5.2 может также находить ориентированный остовный лес для ориентированного графа G= {V, Е), если определить список L[y] узлов, "смежных" с узлом у, как {w\{v, ш) - ребро из £}, т. е. L[v] - это список узлов, которые являются концами ребер с началом у. Пример 5.7. На рис. 5.13,а изображен ориентированный граф, а на рис. 5.13,6 - глубинный остовный лес для него. Как и раньше, мы рисуем древесные ребра сплошными линиями, а прочие ребра - штриховыми. Рис. 5.13. Поиск в г.аубину в ориентированном графе: а - ориентированный граф; б - остовный лес. 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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 0.0021 |