Работа с графами. Лекция 7

Минимальные остовные деревья При разработке электронных схем зачастую необходимо электрически соединить контакты нескольких компонентов. Для соединения множества из n контактов мы можем использовать некоторую компоновку из n 1 проводов, каждый из которых соединяет два контакта. Обычно желательно получить компоновку, которая использует минимальное количество провода. Мы можем смоделировать эту задачу при помощи связного неориентированного графа G = (V, Е), где V множество контактов, Е множество возможных соединений между парами контактов, и для каждого ребра (u, v) Є Е задан вес w(u,v), определяющий стоимость (количество необходимого провода) соединения и и v. 2

Мы хотим найти ациклическое подмножество ТЄЕ, которое соединяет все вершины и чей общий вес минимален. Поскольку множество Т ациклическое и связывает все вершины, оно должно образовывать дерево, которое мы назовем остовным деревом (spanning tree) графа G (иногда используется термин покрывающее дерево). Задачу поиска дерева Т мы назовем задачей поиска минимального остовного дерева (minimum- spanning-tree problem). По сути, термин минимальное остовное дерево означает остовное дерево с минимальным весом. Мы не минимизируем, например, количество ребер в Т, поскольку все остовные деревья имеют ровно |V| 1 ребер. На рис. показан пример связного графа и его минимального остовного дерева. На ребрах указан их вес, а ребра минимального остовного дерева отдельно выделены цветом. Общий вес показанного дерева равен 37. 3

Приведенное дерево не единственное: удалив ребро (b, с) и заменив его ребром (a, h), мы получим другое остовное дерево с тем же весом 37. Далее мы рассмотрим два алгоритма решения задачи поиска минимального остовного дерева алгоритм Крускала (Kruskal) и Прима (Prim). Каждый из них легко реализовать с помощью обычных бинарных пирамид, получив время работы О (E*lgV). При использовании фибоначчиевых пирамид алгоритм Прима можно ускорить до О (Е + VlgV), что является весьма существенным ускорением при |V| << |Е|. 4

Построение минимального остовного дерева Предположим, что у нас есть связный неориентированный граф G = (V, Е) с весовой функцией w : Е R, и мы хотим найти минимальное остовное дерево для G. В этой главе мы рассмотрим два жадных алгоритма решения поставленной задачи. Оба рассматриваемых алгоритма имеют общую схему, согласно которой минимальное остовное дерево растет путем добавления к нему ребер по одному. Алгоритм работает с множеством ребер А, работает следующим образом: Перед каждой очередной итерацией А представляет собой подмножество некоторого минимального остовного дерева. 5

На каждом шаге алгоритма мы определяем ребро (и, v), которое можно добавить к А, в том смысле, что A U {(u,v)} также является подмножеством минимального остовного дерева. Мы назовем такое ребро безопасным (safe edge) для А. Generic_MST(G, W ) 1.А0 2. while А не является минимальным остовным деревом 3. do Найти безопасное для А ребро (и, v) 4. А A U {(u,v)} 5. return А 6

Самое важное, само собой разумеется, заключается в том, как именно найти безопасное ребро в строке 3. Оно должно существовать, поскольку когда выполняется строка 3, требуется, чтобы существовало такое остовное дерево Т, что A Є T. Внутри тела цикла while А должно быть истинным подмножеством Т, поэтому должно существовать ребро (и, v) Є Т, такое что (и, v) не Є А и (и, v) безопасное для А ребро. Далее мы рассмотрим правило для распознавания безопасных ребер и рассмотрим два алгоритма, которые используют это правило для эффективного поиска безопасных ребер. 7

Определения Разрезом (cut) (S, V S) неориентированного графа G = (V, Е) называется разбиение V, что проиллюстрировано на рис. (вершины в множестве S окрашены в черный цвет, а в множестве V S в белый). Мы говорим, что ребро (u,v) Є Е пересекает (crosses) разрез (S, V S), если один из его концов оказывается в множестве S, а второй в V S. Разрез согласован (respect) с множеством А по ребрам, если ни одно ребро из А не пересекает разрез. Ребро, пересекающее разрез, является легким (light), если оно имеет минимальный вес среди всех ребер, пересекающих разрез. 8

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

Правило для распознавания безопасных ребер Теорема. Пусть G = (V, Е) связный неориентированный граф с действительной весовой функцией го, определенной на Е. Пусть А подмножество Е, которое входит в некоторое минимальное остовное дерево G, (S, V S) разрез G, согласованный с Л по ребрам, а (и, v) легкое ребро, пересекающее разрез (5, V S). Тогда ребро (и, v) является безопасным для А. Теорема помогает нам лучше понять, как работает процедура G ENERIC _ MST. В процессе работы алгоритма множество А всегда ациклическое; в противном случае минимальное остовное дерево, включающее А, содержало бы цикл, что приводит к противоречию. 10

В любой момент выполнения алгоритма граф Ga = (V, Е) представляет собой лес и каждый из связных компонентов Gа является деревом. (Некоторые из деревьев могут содержать всего одну вершину, например, в случае, когда алгоритм начинает работу: множество А в этот момент пустое, а лес содержит |V| деревьев, по одному для каждой вершины.) Кроме того, любое безопасное для А ребро (u, v) соединяет различные компоненты G А, поскольку множество A U {(и, и)} должно быть ациклическим. Цикл в строках 2-4 процедуры GENERIC_MST выполняется |V| 1 раз, так как должны быть найдены все |V| 1 ребер минимального остовного дерева. Изначально, когда А = 0, в G А имеется |V| деревьев и каждая итерация уменьшает их количество на единицу. Когда лес содержит только одно дерево, алгоритм завершается. 11

Алгоритмы Крускала и Прима Описанные в этом разделе алгоритмы следуют общей схеме поиска минимального остовного дерева. Каждый из них использует свое правило для определения безопасных ребер в строке 3 процедуры Generic_MST. В алгоритме Крускала множество А является лесом. В А добавляются безопасные ребра, которые являются ребрами минимального веса, объединяющими два различных компонента. В алгоритме Прима множество А образует единое дерево. В А добавляются безопасные ребра, которые являются ребрами минимального веса, соединяющими дерево с вершиной вне дерева. 12

Алгоритм Крускала Алгоритм Крускала непосредственно основан на обобщенном алгоритме поиска минимального остовного дерева. Он находит безопасное ребро для добавления в растущий лес путем поиска ребра (и, v) с минимальным весом среди всех ребер, соединяющих два дерева в лесу. Обозначим два дерева, соединяемые ребром (и, v), как С1 и С2. Поскольку (и, v) должно быть легким ребром, соединяющим С1 с некоторым другим деревом, из следствия 23.2 вытекает, что (и, v) безопасное для С1 ребро. Алгоритм Крускала является жадным, поскольку на каждом шаге он добавляет к лесу ребро с минимально возможным весом. 13

Реализация алгоритма Крускала напоминает алгоритм для вычисления связных компонентов. Она использует структуру для представления непересекающихся множеств. Каждое множество содержит вершины де­рева в текущем лесу. Операция F IND _S ET (u) возвращает представительный элемент множества, содержащего и. Таким образом, мы можем определить, принадлежат ли две вершины и и v одному и тому же дереву, проверяя равенство F IND _S ET (u) и F IND _S ET (v). Объединение деревьев выполняется при помощи процедуры U NION. 14

Реализация доп функций с след слайда 15

1.MST_K RUSKAL (G, w) 2. А 0 3. for (Для) каждой вершины v Є V[G] 4. do M AKE _S ET ( V ) 5. Сортируем ребра из Е в неубывающем порядке их весов w 6. for (Для) каждого (u, v) Є Е (в порядке возрастания веса) 7. do if Find_Set(u) Find_Set(v) 8. then A A U {(u, v)} 9. Union(u, v) 10. return A 16

Алгоритм Крускала работает так, как показано на рис. В строках 1-3 выполняется инициализация множества А пустым множеством и создается \V\ деревьев, каждое из которых содержит по одной вершине. Ребра в Е в строке 4 сортируются согласно их весу в неубывающем порядке. 17

Цикл for в строках 5-8 проверяет для каждого ребра (и, v), принадлежат ли его концы одному и тому же дереву. Если это так, то данное ребро не может быть добавлено к лесу без того, чтобы создать при этом цикл, поэтому в таком случае ребро отбрасывается. 18

19

В противном случае, когда концы ребра принадлежат разным деревьям, в строке 7 ребро (и, v) добавляется в множество А, и вершины двух деревьев объединяются в строке 8. Время работы алгоритма Крускала для графа G = {V,E) зависит от реализации структуры данных для непересекающихся множеств. Инициализация множества А в строке 1 занимает время 0(1), а время, необходимое для сортировки множества в строке 4, равно О (ElgE). Цикл for в строках 5-8 выполняет О (Е) операций F IND _S ET и U NION над лесом непересекающихся множеств. 20

Вместе с |V| операциями M AKE _S ET эта работа требует времени О ((V + Е) *а (V)), где а очень медленно растущая функция. Поскольку мы предполагаем, что G связный граф, справедливо соотношение |E| |V| 1, так что операции над непересекающимися множествами требуют О (Е*а(V)) времени. Кроме того, поскольку a(|V|) = О (lg V) = О (lg Е), общее время работы алгоритма Крускала равно О (ElgE). Заметим, что |E| < |V| 2, поэтому lg|E| = О (lg V) и время работы алгоритма Крускала можно записать как О (Е lg V). 21

Алгоритм Прима Аналогично алгоритму Крускала, алгоритм Прима представляет собой част­ный случай обобщенного алгоритма поиска минимального остовного дерева. Алгоритм Прима очень похож на алгоритм Дейкстры для поиска кратчайшего пути в графе. Алгоритм Прима обладает тем свойством, что ребра в множестве А всегда образуют единое дерево. Как показано на след. слайде, дерево начинается с произвольной корневой вершины r и растет до тех пор, пока не охватит все вершины в V. На каждом шаге к дереву А добавляется легкое ребро, соединяющее дерево и отдельную вершину из оставшейся части графа. 22

В соответствии со следствием, данное правило добавляет только безопасные для А ребра; следовательно, по завершении алгоритма ребра в А образуют минимальное остовное дерево. 23

Следствие из теоремы: Пусть G = (V,E) связный неориентированный граф с действительной весовой функцией w, определенной на Е. Пусть А подмножество Е, которое входит в некоторое минимальное остовное дерево G, и пусть С = (Vc,Ec) связный компонент (дерево) в лесу G A = (V, А). Если (u,v) легкое ребро, соединяющее С с некоторым другим компонентом в G A, то ребро (и, v) безопасно для А. 24

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

В процессе работы алгоритма все вершины, которые не входят в дерево, располагаются в очереди с приоритетами Q, основанной на значении поля key, причем меньшее значение этого поля означает более высокий приоритет в очереди. Для каждой вершины v значение поля key [v] представляет собой минимальный вес среди всех ребер, соединяющих v с вершиной в дереве. Если ни одного такого ребра нет, считаем, что key [v] =. Поле π[v] указывает родителя v в дереве. В процессе работы алгоритма множество А из процедуры Generic_MST неявно поддерживается как А = {(v, π[v]) : v Є V {r} Q}. 26

Когда алгоритм завершает работу, очередь с приоритетами Q пуста и минимальным остовным деревом для G является дерево А = {(v, π[v]) : v Є V {r} }. MST_Prim(G, w, г) for (Для) каждой вершины и Є V[G] do key [и] π[u] NIL key[г] 0 Q V[G] while Q 0 do и E XTRACT _M IN (Q) for (Для) каждой вершины v Є Adj [u] do if v Є Q и w(u, v) < key[v] then π[v] и key[v] w(u, v) 27

Работа алгоритма Прима проиллюстрирована на рис. В строках 1-5 ключи всех вершин устанавливаются равными (за исключением корня r, ключ которого равен 0, так что он оказывается первой обрабатываемой вершиной), указателям на родителей для всех узлов присваиваются значения NIL и все вершины вносятся в очередь с приоритетами Q. Алгоритм поддерживает следующий инвариант цикла, состоящий из трех частей. 1. Перед каждой итерацией цикла while в строках 6-11 А = {(v, π[v]) : v Є V {г} Q}; 2.вершины, уже помещенные в минимальное остовное дерево, принадлежат множеству V Q; 3. для всех вершин V ЄQ справедливо следующее: если π [v] NIL, то key [v] < и key [v] вес легкого ребра (v, π [v]), соединяющего v с некоторой вершиной, уже находящейся в минимальном остовном дереве. 28

В строке 7 определяется вершина и, принадлежащая легкому ребру, пересекающему разрез (V Q, Q) (за исключением первой итерации, когда и = г в со­ответствии с присвоением в строке 4). Удаление и из множества Q добавляет его в множество V Q вершин дерева. Цикл for в строках 8-11 обновляет поля key и π для каждой вершины v, смежной с и и не находящейся в дереве. Это обновление сохраняет третью часть инварианта. 29

Производительность алгоритма Прима зависит от выбранной реализации очереди с приоритетами Q. Если реализовать ее как бинарную пирамиду, то для выполнения инициализации в строках 1-5 можно использовать процедуру B UILD _M IN _H EAP, что потребует времени О (V). Тело цикла while выполняется |V| раз, а поскольку каждая операция EXTRACT_MlN занимает время О (lg V), общее время всех вызовов процедур EXTRACT_MlN составляет О (V lg V). Цикл for в строках 8-11 выполняется всего О (Е) раз, поскольку сумма длин всех списков смежности равна 2 \Е\. Внутри цикла for проверка на принадлежность Q в строке 9 может быть реализована за постоянное время, если воспользоваться для каждой вершины битом, указывающим, находится ли она в Q, и обновлять этот бит при удалении вершины из Q. Присвоение в строке 11 неявно включает операцию DECREASE_KEY над пирамидой. 30

Время выполнения этой операции О (lg V). Таким образом, общее время работы алгоритма Прима составляет О(V lgV + E lgV) = О (E lgV), что асимптотически совпадает со временем работы рассмотренного ранее алгоритма Крускала. Однако асимптотическое время работы алгоритма Прима можно улучшить за счет применения фибоначчиевых пирамид. Если |V| элементов организованы в фибоначчиеву пирамиду, то операцию EXCTRACT_MIN можно выполнить за амортизированное время O(lgV), а операцию DECREASE_ K EY за амортизированное время 0(1). Следовательно, при использовании фибоначчиевой пирамиды для реализации очереди с приоритетами Q общее время работы алгоритма Прима улучшается до О (Е + V lg V). 31

Заключительные замечания Книга Таржана (Tarjan) содержит превосходный обзор задач, связан­ных с поиском минимальных остовных деревьев, и дополнительную информацию о них. История данной задачи изложена Грехемом (Graham) и Хеллом (Hell). Таржан указывает, что впервые алгоритм для поиска минимальных остовных деревьев был описан в 1926 году в статье Борувки (О. Bonivka). Алгоритм Крускала описан в 1956 году, а алгоритм, извест­ный как алгоритм Прима, в работе Прима (Prim), хотя до этого он был открыт Ярником (Jamik) в 1930 году. 32