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

Ребро

Стоимость

Ребро

Стоимость

{Vl, V,)

(f2. v)

{Vi, fe)

(fa. fs)

{Vb, Ve)

(Ve, v)

Разумеется, на самом деле на шаге 3 алгоритма 5.1 ребра не сортируются, а хранятся в виде сортирующего дерева, 2-3-дерева или какой-нибудь другой приемлемой структуры данных, пока они не потребуются. Сортирующее дерево из разд. 3.4 фактически дает идеальный способ реализации очереди с приоритетами. Повторное обращение в строке 6 с целью найти ребро наименьшей стоимости является основной операцией с Сортдеревом. Кроме того, число ребер, выбираемых в строке 6 для построения остовного дерева, часто меньше \\Е\\. В таких ситуациях мы экономим время, поскольку никогда не упорядочиваем Е полностью.

Вначале каждое ребро находится в одноэлементном множестве, входящем в yS и состоящем из самого этого ребра. Наименьшую стоимость имеет ребро (vi, v), так что оно добавляется к дереву и множества {Vi) и {у,} в VS сливаются.

Затем рассматривается ребро (из, Vt). Так как Va и и* принадлежат разным множествам из VS, добавляем (Уз, v) к дереву и сливаем {vs} и {v}. Далее добавляем {Vi, U7} и сливаем {и} с {vu Vi). Добавляем также четвертое ребро {из, у,} и сливаем {vi, v, v,} G {v», Vi}.


Рис. 5.3. Неориентированный граф с указанными стоимостями его ребер.



Ребро

Действие

Множества в VS (связные подграфы)

Добавить

V,}, Ы. Ы. Ы, {v,\, {v,\

Добавить

Добавить

V2, Щ\, iv„ у,}, {у,}, {у,}

(Уз.

Добавить

V,, Уз. у.. V,}, {у.}, {у,}

(V-i,

Отвергнуть

Отвергнуть

Добавить

Vi, Уз. 4. «Б. V,\, {у,}

Отвергнуть

(Vl,

Добавить

.... щ\

Рис. 5.4. Последовательность шагов построения остовного дерева.

Затем рассматривается ребро (у,, Уз). Оба узла у, и Уз принадлежат одному и тому же множеству {у1, Уа, Уз, «4, v-,}. Следовательно, из Уа в Уз идет путь из ребер, уже вошедших в остовное дерево, и потому (Уа, Уз) не добавляется. Вся последовательность шагов приведена на рис. 5.4. Остовное дерево, получающееся в результате, изображено на рис. 5.5. □

Теорема 5.1. Алгоритм 5.1 находит остовное дерево наименьшей стоимости для связного графа G. Если в цикле, описанном строками 5-10, рассматривается d ребер, пю затрачивается время 0(d\oge), где е=£. Следовательно, алгоритм 5.1 занимает не более О (с log с) времени.

Доказательство. Корректность алгоритма вытекает непосредственно из леммы 5.2 и того факта, что строки 8 и 9 сохраняют узлы в том же самом множестве тогда и только тогда, когда


Рис. 5.5. Остовное дерево наименьшей стоимости.



они принадлежат одному и тому же дереву остовного леса, представленного набором VS.

Для оценки времени допустим, что требуется d итераций цикла в строках 5-10. Нахождение ребра наименьшей стоимости в Q (строка 6) занимает О (logе) шагов, если Q реализуется очередью с приоритетами. Общее время нахождения всех множеств Wi и Wt, содержащих v н w (строка 8), и замены их на их объединение (строка 9) не превосходит О (eG (е)) ), если применяется быстрый алгоритм объединения непересекающихся множеств. Остальная часть цикла, очевидно, занимает постоянное время, не зависящее от размера G. Засылка начальных данных в Q занимает время 0(e), а в VS - время О (п), где п - число узлов в V. □

5.2. МЕТОД ПОИСКА В ГЛУБИНУ

Рассмотрим прохождение узлов неориентированного графа в следующем порядке. Выбираем и "посещаем" некоторый начальный узел V. Затем выбираем произвольное ребро (v, w), инцидентное v, и посещаем ш. Вообще пусть х - последний посещенный узел. Для продолжения процесса выбираем какое-нибудь не рассмотренное еще ребро (х, у), инцидентное х. Если узел у уже посещался, ищем другое новое ребро, инцидентное х. Если у раньше не посещался, идем в и заново начинаем поиск от узла у. Пройдя все пути, начинающиеся в узле у, возвращаемся в х, т. е. в тот узел, из которого впервые был достигнут узел у. Затем продолжаем выбор нерассмотренных ребер, инцидентных узлу х, до тех пор, пока не будет исчерпан список этих ребер. Этот метод обхода узлов неориентированного графа называется поиском в глубину, поскольку процесс поиска идет в направлении вперед (вглубь) до тех пор, пока это возможно.

Поиск в глубину можно также осуществлять и на ориентированном графе. Если граф ориентирован, то, находясь в узле х, мы выбираем ребра (х, у), только выходящие из х. Исследовав все ребра, выходящие из у, мы возвращаемся в х даже тогда, когда в у входят другие ребра, еще не рассмотренные.

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

Поиск в глубину на неориентированном графе G= (V, Е) разбивает ребра, составляющие Е, на два множества Г и В. Ребро (у, ш) помещается в множество Т, если узел ш не посещался до того момента, когда мы, рассматривая ребро (о, ш), оказались в узле v.

) Здесь G -функция, введенная в разд. 4.7,-Прим. ред.





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.002