Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[161]

24.2. Алгоритмы Крускала и Прима

Оба этих алгоритма следуют описанной схеме, но по-разному выбирают безопасное ребро. В алгоритме Крускала множество рёбер А представляет собой лес, состоящий из нескольких связных компонент (деревьев). Добавляется ребро минимального веса среди всех рёбер, концы которых лежат в разных компонентах.

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

Алгоритм Крускала

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

Пусть (и, v) - такое ребро, соединяющее вершины из компонент С\ и CV Это ребро является лёгким ребром для разреза С\, V\C\, и можно воспользоваться теоремой 24.1 (или прямо следствием 24.2).

Реализация алгоритма Крускала напоминает алгоритм вычисления связных компонент (разд. 22.1) и использует структуры данных для непересекающихся множеств (гл. 22), Элементами множеств являются вершины графа. Напомним, что Find-Set(m) возвращает представителя множества, содержащего элемент и. Две вершины и и v принадлежат одному множеству (компоненте), если Find-Set (и) = Find-Set (и). Объединение деревьев выполняется процедурой Union.

\textsc{MST-Kruskal}$(G,w)$

1$A \leftarrow \emptyset$

2{\bf for} $v\in V[G]$

3{\bf do} \textsc{Make-Set}$(v)$

4упорядочить р\"~~а5бра $E$ по весам

5{\bf for} $(u,v)\in E$ (в порядке возрастания веса)

6{\bf do if} \textsc{Find-Set}$(u) \noteq$ \textsc{Find-Set}$(v)$

7{\bf then} $A \leftarrow A \cup \{(u,v)\}$

8\textsc{Union} $(u,v)$

9{\bf return} $A$

На рисунке 24.4 показа работа алгоритма. Сначала (строки 1-3) множество А пусто, и есть \V\ деревьев, каждое из которых содержит по одной вершине. В строке 4 рёбра из Е упорядочиваются по неубыванию веса. В цикле (строки 5-8) мы проверяем, лежат


Рис. 24.4 24.4 Работа алгоритма Крускала на графе рис. 24.1. Рёбра растущего леса (А) выделены серым цветом. Рёбра рассматриваются в порядке неубывания весов (текущее ребро показано стрелкой). Если ребро соединяет два различных дерева, оно добавляется к лесу, а деревья сливаются.

ли концы ребра в одном дереве. Если да, то ребро нельзя добавить к лесу (не создавая цикла), и оно отбрасывается. Если нет, то ребро добавляется к А (строка 7), и два соединённых им дерева объединяются в одно (строка 8).

Подсчитаем время работы алгоритма Крускала. Будем считать, что для хранения непересекающихся множеств используется метод раздела 22.3 (с объединением по рангу и сжатием путей - самый быстрый из известных). Инициализация занимает время 0(V), упорядочение рёбер в строке 4 - O(ElgE). Далее производится О(Е) операций, в совокупности занимающих время 0(Еа(Е,V)), где а - функция, обратная к функции Аккермана (см. раздел 22.4). Поскольку а(Е, V) = o(lgE), общее время работы алгоритма Крускала составляет O(ElgE) (основное время уходит на сортировку).

Алгоритм Прима

Как и алгоритм Крускала, алгоритм Прима следует общей схеме алгоритма построения минимального остова из раздела 24.1. Он похож на алгоритм Дейкстры поиска кратчайшего пути в графе (раздел 25.2). В этом алгоритме растущая часть остова представляет собой дерево (множество рёбер которого есть А). Как показано на рис. 24.5, формирование дерева начинается с произвольной корневой вершины г. На каждом шаге добавляется ребро наименьшего веса среди рёбер соединяющих вершины этого дерева с вершинами не из дерева. По следствию 24.2 такие рёбра являются безопасными для А, так что в результате получается минимальный остов.

При реализации важно быстро выбирать лёгкое ребро. Алгоритм получает на вход связный граф G и корень г минимального покрывающего дерева. В ходе алгоритма все вершины, ещё не попавшие в дерево, хранятся в очереди с приоритетами. Приоритет вершины v определяется значением key[v], которое равно минимальному весу рёбер, соединяющих v с вершинами дерева А. (Если таких рёбер нет, полагаем key[v] = оо.) Поле ir[v] для вершин дерева указывает на родителя, а для вершины v £ Q указывает на вершину дерева, в которую ведёт ребро веса fcet/[u] (одно из таких рёбер, если их несколько). Мы не храним множество А вершин строимого дерева явно; его можно восстановить как

A = {(v,jr[v]):veV\{r}\Q}.

В конец работы алгоритма очередь Q пуста, и множество

A = {(v,n[v]):veV\{r}}.


Рис. 24.5 24.5 Работа алгоритма Прима на графе рис. 24.1 с корневой вершиной а Рёбра, входящие в дерево А. выделены серым; вершины дерева - чёрным. На каждом шаге к А добавляется ребро, пересекающее разрез между деревом и его дополнением. Например, на втором шаге можно было бы добавить любое из рёбер (Ь, с) и (а, К).

есть множество вершин покрывающего дерева.

\textsc{MST-Prim}$(G,W,г)$

1$Q \leftarrow V[G]$

2{\bf for} $u\in Q$

3{\bf do} $key[u] \gets \infty$

4$key[r] \gets 0$

5$\pi[r] \gets \textsc{nil}$

6{\bf while} $Q \noteq \emptyset$

7{\bf do} $u \leftarrow \textsc{Extract-Min}(Q)$

8{\bf for} $v\in Adj[u]$

9{\bf do if} $v\in Q$ и $w(u,v)<key[v]$

10{\bf then} $\pi(v) \leftarrow u$

11$key(v) \leftarrow w(u,v)$

На рис. 24.5 показана работа алгоритма Прима. После исполнения строк 1-5 и первого прохода цикла в строках 6--11 дерево

состоит из единственной вершины г, все остальные вершины находятся в очереди, и значение &ey[u] для них равно длине ребра из г в v или +оо, если такого ребра нет (в первом случае ir[v] = г. Таким образом, выполнен описанный выше инвариант (дерево есть часть некоторого остова, для вершин дерева поле тг указывает на родителя, а для остальных вершин на «ближайшую» вершину дерева - вес ребра до неё хранится в &еи[и].

Время работы алгоритма Прима зависит от того, как равлизо-вана очередь Q. Если использовать двоичную кучу (глава 7), инициализацию в строках 1-4 можно выполнить с помощью процедуры Build-Heap за время 0(V). Далее цикл выполняется \V\ раз, и каждая операция Extract-Min занимает время 0(lgV), всего 0(V\gV). Цикл for в строках 8-11 выполняется в общей сложности О(Е) раз, поскольку сумма степеней вершин графа равна 2\Е\. Проверку принадлежности в строке 9 внутри цикла for можно реализовать за время 0(1), если хранить состояние очереди ещё и как битовый вектор размера \V\. Присваивание в строке 11 подразумевает выполнение операции уменьшения ключа (Decrease-Key), которая для двоичной кучи может быть выполнена за время 0(lgV). Таким образом, всего получаем 0(V lg V + Elg V) = 0(E\gV) - та же самая оценка, что была для алгоритма Крускала.

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



[стр.Начало] [стр.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] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]