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

Введение

 

         Задача о нахождении минимального  остовного дерева часто встречается  в подобной постановке: есть n городов, через которые можно проложить маршрут так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Требуется найти такой маршрут, чтобы стоимость проезда была максимальной.

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

Существует  несколько алгоритмов для нахождения минимального остовного дерева. Некоторые  наиболее известные из них перечислены  ниже:

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

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

-   Алгоритм Борувки.

В данной курсовой работе подробно будет рассмотрен алгоритм Краскала.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Анализ и теоретическое исследование  алгоритма.

 

1.1 Постановка задачи.

 

В ходе выполнения данного курсового проекта необходимо разработать программный код  построения минимального остовного дерева по алгоритму Краскала. Экспериментально и теоретически вычислить среднюю трудоемкость алгоритма, затем сравнить полученные значения. 

 

1.2 Основные понятия теории графов.

 

Граф  – система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий(геометрический способ задания графа – см. рисунок 1). Кружки называются вершинами графа, линии со стрелками – дугами, безстрелок – ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линииявляются дугами) называется ориентированным.

Рис. 1. Пример графа

 

Теория графов может рассматриваться как раздел дискретной математики (точнее – теории множеств), и формальное определение графа таково: задано конечное множество X, состоящее из nэлементов (X = {1, 2, ..., n}), называемых вершинами графа, и подмножество V декартова произведения , то есть называется совокупность (X, V) (неориентированным графом называется совокупность множества X и множества неупорядоченныхпар элементов, каждый из которых принадлежит множеству X).Дугу между вершинами i и j, i, j X, будем обозначать (i, j). Число дуг графа будем обозначать m (V =

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

Две вершины  называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) – инцидентным соответствующим вершинам. Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги. Простой путь – путь, в котором ни одна дуга не встречается дважды. Элементарный путь – путь, в котором ни одна вершина не встречается дважды. Контур – путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура)  называется число дуг пути (или сумма длин его дуг, если последние заданы).   Граф, для которого из (i, j) V следует (j, i) V называетсясимметрическим. Если из (i, j) V следует, что (j, i) V, то соответствующий граф называется антисимметрическим.Цепью называется множество ребер (в неориентированномграфе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого.Замкнутаяцепь называется циклом.Если любые две вершины графа можно соединить цепью, тограф называется связным. Если граф не является связным, то егоможно разбить на связные подграфы, называемые компонентами. Связностью графа называется минимальное число ребер, после удаления которых граф становится несвязным. Для ориентированных графов, если любые две вершины графа можно соединитьпутем, то граф называется сильно связным. Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m = n – 1, а число висячих вершин равно .

1.3 Минимальные остовные деревья.

 

Минимальным остовным деревом (МОД) связного взвешенного  графа называется его связный  подграф, состоящий из всех вершин исходного  дерева и некоторых его ребер, причем сумма весов ребер максимально  возможная. Если исходный граф несвязен, то описываемую ниже процедуру можно  применять поочередно к каждой его  компоненте связности, получая тем  самым минимальные остовные деревья  для этих компонент.

При разработке ,например, электронных схем зачастую необходимо электрически соединить  контакты нескольких компонентов. Для  соединения множества из n контактов можем использовать некоторую компоновку из n-1  проводов, каждый из которых соединяет два контакта. Обычно желательно получить компоновку, которая использует минимальное количество провода.

Мы можем  смоделировать эту задачу при  помощи связного неориентированного графа  G = (V, E), где V-множество контактов, E-множество возможных соединения между парами контактов, и для каждого ребра

(u,v) ∈E задан вес w (u,v), определяющий стоимость (количество необходимого провода) соединения  u и v. Нам нужно найти ациклическое подмножество TE, которое соединяет все вершины и чей общий вес минимален. Поскольку множество Т ациклическое и связывает ве вершины, оно должно образовать дерево, которое мы назовем остовным деревом графа G. Задачу поиска дерева Т мы назовем задачей поиска минимального остовного дерева. На рис.2  Показан пример связного графа и его минимального остовного дерева. На ребрах указан их вес , а ребра минимального остовного дерева отдельно выделены цветом. Общий вес показанного дерева равен 37.

 

Рис. 2 Минимальное оставное дерево связанного графа.

 

Приведенное дерево не единственное: удалин ребро (b, c) и заменив его ребром (a, h), мы получин другое остовное дерево с тем же весом 37.

 

1.4 Построение минимального остовного дерева.

 

Рассмотрим  общую схему работы алгоритмов построения минимального остовного дерева с  использованием жадной стратегии. Итак, пусть дан связный неориентированный  граф G=(V;E) c n вершинами и весовая функция w: E → R.

Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграфА исходного графа G, который называется промежуточным остовным лесом. Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое ребро e=(u,v) выбирается так, чтобы не нарушить этого свойства: A∪ {e} тоже должно быть подграфом минимального. Такое ребро называется безопасным.

Вот как выглядит общий алгоритм построения минимального остовного  дерева:

MST-GENERIC(G,w) 
1: A ← 0 
2: while (пока) A не является остовом 
3:     do найти безопасное ребро (u,v) ∈E для A 
4:         A ← A∪ {(u,v)} 
5: returnA

По определению A, он должен оставаться подграфом некоторого минимального остова после любого числа итераций. Конечно, главный вопрос состоит в том, как искать безопасное ребро на шаге 3. Понятно, что такое ребро всегда существует, если A еще не является минимальным остовом (любое ребро остова, не входящее в A). Заметим, что так как A не может содержать циклов, то на каждом шаге ребром соединяются различные компоненты связности (изначально все вершины в отдельных компонентах, в конце A – одна компонента). Таким образом цикл выполняется (n-1) раз.

Далее приводится общее правило  отыскания безопасных ребер. Для  этого доказана теорема, которая  поможет находить безопасные ребра. Предварительно докажем маленькую  лемму:

Лемма: пусть Т – минимальное остовное дерево. Тогда любое ребро е из T – безопасное.  
Док-во: в Т – (n-1) ребро. На каждом шаге Generic-MST мы добавляли одно безопасное ребро. Всего выполнено (n-1) шагов, следовательно, все ребра в T – безопасные по определению.

Теорема: Пусть G(V;E) – связный неориентированный граф и на множестве Е определена весовая функция w. Пусть А – некоторый подграф G, являющийся в то же время подграфом некоторого минимального остовного дерева T. Рассмотрим компоненту связности К из А. Рассмотрим множество E(K) ребер графа G, только один конец которых лежит в К. Тогда ребро минимального веса из E(K) будет безопасным.  
Док-во: Пусть e=(u,v) – минимальное по весу ребро из E(K). Пусть минимальный остов T не содержит e (в противном случае доказываемое утверждение очевидно по приведенной выше лемме). Т.к. T связен, в нем существует некоторый (единственный) ациклический путь p из u в v, и e замыкает его в цикл. Поскольку один из концов e лежит в K, а другой в V \ K, в пути p существует хотя бы одно ребро e'=(x,y), которое обладает тем же свойством. Это ребро не лежит в A, т.к. в A пока что нет ребер между K и V \ K. Удалим из T ребро e' и добавим e. Так как w(e') <w(e), мы получим остовное дерево T', суммарный вес которого меньше суммарного веса T. Таким образом, T не является минимальным остовом. Противоречие. Следовательно, T содержит e.

В связи с приведенной теоремой введем следующее 

Определение.Безопасным ребром e относительно некоторой компоненты связности К из А назовем ребро с минимальным весом, ровно один конец которого лежит в К.

 

1.5 Теоретическое исследование Алгоритм Краскала.

 

Алгоритм  Краскала объединяет вершины графа  в несколько связных компонент, каждая из которых является деревом. На каждом шаге из всех ребер, соединяющих  вершины из различных компонент  связности, выбирается ребро с наименьшим весом. Необходимо проверить, что оно  является безопасным. Безопасность ребра  гарантируется ранее доказанной теоремой о безопасных ребрах. Так  как ребро является самым легким из всех ребер, выходящих из данной компоненты, оно будет безопасным.

Остается понять, как реализовать  выбор безопасного ребра на каждом шаге. Для этого в алгоритме Краскала все ребра графа G перебираются по возрастанию веса. Для очередного ребра проверяется, не лежат ли концы ребра в разных компонентах связности, и если это так, ребро добавляется, и компоненты объединяются.

Удобно использовать для хранения компонент структуры данных для  непересекающихся множеств, как, например, списки или, что лучше, лес непересекающихся множеств со сжатием путей и объединением по рангу (один из самых быстрых известных  методов). Элементами множеств являются вершины графа, каждое множество  содержит вершины одной связной  компоненты. Для работы с множествами  используются следующие процедуры:

Make-Set(v)	Создание множества из набора вершин
Find-Set(v)	Возвращает множество, содержащее данную вершину
Union(u,v)	Объединяет множества, содержащие данные вершины

 

 

Общая схема алгоритма выглядит так:

MST-KRUSKAL(G,w) 
1: A ← 0 
2: for each (для каждой) вершины v∈V[G]  
3:     do Make-Set(v) 
4: упорядочить ребра по весам 
5: for (u,v) ∈E (в порядке возрастания веса) 
6:     do if Find-Set(u) ≠ Find-Set(v) then 
7:         A ← A∪ {(u,v)} 
8:         Union(u,v) 
9: returnA

Пример:

На рисунках К1-К8 представлена работа алгоритма.

Рис. К1. Начальная фаза. Минимальный  покрывающий лес пуст.	Рис. К2. Перебираем ребра в порядке  возрастания веса: первое ребро с  весом 2. Добавляем его к А.
Рис. К3. Следующее безопасное ребро  с весом 6. Добавляем его.	Рис. К4.
Рис. К5.	Рис. К6.
Рис. К7.	Рис. К8. Ребра с весом 17, 19 и 25 –  не безопасные. Их концы лежат в  одной компоненте связности. Ребро  с весом 21 – безопасное, поэтому  добавляем его. Минимальное остовное дерево построено.

Подсчитаем  время работы алгоритма. Будем считать, что для хранения непересекающихся множеств используется метод с объединением по рангу и сжатием путей, т.к. это самый быстрый способ из известных  на сегодняшний день. Инициализация  занимает время O(V), упорядочение ребер в строке 4 – O(ElogE). Далее производится O(E) операций, в совокупности занимающих время O(Eα’(E,V)), где α’ - функция, обратная к функции Аккермана .Поскольку α’(E,V) = o(logE), общее время работы алгоритма Крускала составляет O(ElogE) (основное время уходит на сортировку).

 

 

 

1.6 Теоретическая оценка трудоемкости  алгоритма Краскала.

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

Под элементарными операциями языка  высокого уровня, будем понимать операции которые могут быть представлены в виде элементарных конструкций  данного языка (но не обязательно  в виде одной машинной команды), а  именно за одну элементарную операцию будем считать следующие:

1) операцию присваивания  a¬b;

2) операцию индексации массива a[i];

3) арифметические операции   *,/,-,+;

4) операции сравнения    a<b;

5) логические операции   or,and,not.

Отметим, что неявно в операцию сравнения входит машинная команда  перехода в конструкции ifthenelse:

F _{«ветвление»} = f_then * p  +f_else * (1-p).

Цикл не является элементарной операцией, т.к. может быть представлен в  виде;