Міністерство освіти і науки України
Сумський державний університет
Кафедра Інформатики
Курсова робота
з дисципліни
"Теорія алгоритмів та математична логіка "
на тему:
"Алгоритми пошуку остовного дерева Прима і Крускала "
Суми 2006
Зміст
Завдання
Вступ
1. Теоретична частина
2. Практична реалізація
Висновок
Програмний код
Література
Завдання
Розробити програмну реалізацію рішення задачі про мінімальний покриває дереві (побудова мінімального кістяка). Для знаходження мінімального покриває дерева використовувати алгоритми Прима та Крускала.
Вихідна інформація про ребрах графа знаходиться в текстовому файлі dan.txt.
Вступ
Нехай мається зв'язний неорієнтовані граф G = (V, Е), в якому V - безліч контактів, а E - безліч їх можливих попарних сполучень. Для кожного ребра графа (u, v) задано вага w (u, v) (довжина дроту, необхідного для з'єднання u і v). Завдання полягає в знаходженні підмножини Т Е, що зв'язує всі вершини, для якого сумарна вага мінімальний.
w (T) = w (u, v)
Таке підмножина Т буде деревом (оскільки не має циклів: в будь-якому циклі один з проводів можна видалити, не порушуючи зв'язності). Зв'язний подграф графа G, що є деревом і містить всі його вершини, називають покриваючим деревом цього графа. (Іноді використовують термін "остовне дерево"; для стислості ми будемо говорити просто "кістяк".)
Далі ми розглянемо задачу про мінімальний покриває дереві. (Тут слово "мінімальне" означає "має мінімально можливий вага".)
Рис 1
На Рис 1 показано на прикладі мінімальне покриває дерево. На кожному ребрі графа вказана вага. Виділено ребра мінімального покриває дерева (Сумарна вага 37). Таке дерево не єдино: замінюючи ребро (Ь, с) ребром (а, h), отримуємо інше дерево тієї ж ваги 37.
Ми розглянемо два способи рішення задачі про мінімальний покриває дереві: алгоритми Крускала і Прима. Кожен їх них легко реалізувати з часом роботи O (E logV), використовуючи звичайні двійкові купи. Застосувавши фібоначчіеви купи, можна скоротити час роботи алгоритму Прима до O (E + V logV) (що менше Е logV, якщо | V | багато менше Е ).
Обидва алгоритму слідують "жадібної" стратегії: на кожному кроці вибирається "локально найкращий "варіант. Не для всіх задач такий вибір приведе до оптимального рішенням, але для задачі про покриваючому дереві це так. Тут буде описана загальна схема алгоритму побудови мінімального кістяка (додавання ребер одного за іншим). Надалі будуть зазначені дві конкретних реалізації загальної схеми.
Отже, нехай дано зв'язний неорієнтовані граф G = (V, Е) і вагова функція w: Є. Ми хочемо знайти мінімальне покриває дерево (остов), слідуючи жадібної стратегії.
Загальна схема всіх наших алгоритмів буде така. Шуканий остов будується поступово: до спочатку пустому безлічі А на кожному кроці додається одне ребро. Безліч А завжди є підмножиною деякого мінімального кістяка. Ребро (u, v), що додається на черговому кроці, вибирається так, щоб не порушити цієї властивості: А {(u, v)} теж має бути підмножиною мінімального кістяка. Ми називаємо таке ребро безпечним ребром для А.
Generic-MST (G, w)
1 А
2 while A не є остовом
3 do знайти безпечне ребро (u, v) для А
4 А A {(u, v)}
5 return A
Рис. 2. Два зображення одного і того ж розрізу графа з Рис 1.
(а) Вершини множини S зображені чорними, його доповнення V S - білим. Ребра, перетинають розріз, з'єднують білі вершини з чорними. Єдине легке ребро, що перетинає розріз - ребро (d, с). Безліч А складається з сірих ребер. Розріз (s, V S) узгоджений з А (жодне ребро з А не перетинає розріз).
(Ь) Вершини множини S зображені ліворуч, вершини V S - праворуч. Ребро перетинає розріз, якщо воно перетинає вертикальну пряму.
За визначенню безпечного ребра властивість "А є підмножиною деякого мінімального кістяка "(для порожнього безлічі це властивість, очевидно, виконано) залишається істинним для будь-якого числа ітерацій циклу, так що в рядку 5 алгоритм видає мінімальний остов. Звичайно, головний питання в тому, як шукати безпечне ребро в рядку 3. Таке ребро існує (Якщо А є підмножиною мінімального кістяка, то будь ребро цього остова, що не входить в А, є безпечним). Зауважимо, що безліч А не може містити циклів (оскільки є частиною мінімального кістяка). Тому добавляемое у рядку 4 ребро з'єднує різні компоненти графа G a = (V, A), і з кожною ітерацією циклу число компонент зменшується на 1. Спочатку кожна точка являє собою окрему компоненту; наприкінці весь остов - одна компонента, так що цикл повторюється | V | - 1 раз.
Теоретична частина
Алгоритм Крускала
У будь-який момент роботи алгоритму Крускала безліч А обраних ребер (частина майбутнього кістяка) не містить циклів. Воно з'єднує вершини графа в кілька зв'язкових компонент, кожна з яких є деревом. Серед всіх ребер, що з'єднують вершини з різних компонент, береться ребро найменшої ваги. Треба перевірити, що воно є безпечним.
Нехай (u, v) - таке ребро, з'єднує вершини з компонент С 1 і C 2 - Це ребро є легким ребром для розрізу (С 1 , V C 1 ).
Реалізація алгоритму Крускала використовує структури даних для непересічних множин. Елементами множин є вершини графа. Нагадаємо, що Find-Set (u) повертає представника безлічі, що містить елемент u. Дві вершини u і v належать одному безлічі (компоненті), якщо Find-Set (u) = Find-Set (v). Об'єднання дерев виконується процедурою Union. (Строго кажучи, процедурам Find-Set і Union повинні передаватися покажчики на u і v)
MST-Kruskal (G, w)
1 A
2 for кожної вершини v V [G]
3 do Make-Set (v)
4 упорядкувати ребра Е по вагам
5 for (u, v) E (у порядку зростання ваги)
6 do if Find-Set (u) Find-Set (v)
7 then A: = A {(u, v)}
8 Union (u, v)
9 return A
Спочатку (рядки 1-3) безліч А порожньо, і є | V | дерев, кожне з яких містить по одній вершині. У рядку 4 ребра з Е упорядковуються по неубиванію ваги. У циклі (рядки 5-8) ми перевіряємо, чи лежать кінці ребра в одному дереві. Якщо так, то ребро не можна додати до лісу (не створюючи циклу), і воно відкидається. Якщо ні, то ребро додається до А (рядок 7), і два з'єднаних їм дерева об'єднуються в одне (рядок 8).
Підрахуємо час роботи алгоритму Крускала. Будемо вважати, що для зберігання непересічних множин використовується метод з об'єднанням за рангом і стисненням шляхів - найшвидший з відомих. Ініціалізація займає час O (V), упорядкування ребер у рядку 4 - O (E logE). Далі проводиться O (Е) операцій, в сукупності займають час О (Е (Е, V)). (Основний час йде на сортування).
Алгоритм Прима
Як і алгоритм Крускала, алгоритм Прима відповідає загальній схемі алгоритму побудови мінімального кістяка. У цьому алгоритмі зростаюча частина кістяка представляє собою дерево (безліч ребер якого є А). Формування дерева починається з довільною кореневої вершини r. На кожному кроці додається ребро найменшої ваги серед ребер з'єднують вершини цього дерева з вершинами не з дерева. По слідству такі ребра є безпечними для А, так що в результаті виходить мінімальний остов.
При реалізації важливо швидко вибирати легке ребро. Алгоритм отримує на вхід зв'язний граф G і корінь r мінімального покриває дерева. В ході алгоритму всі вершини, ще не потрапили в дерево, зберігаються в черзі з пріоритетами. Пріоритет вершини v визначається значенням key [u], яке дорівнює мінімальної ваги ребер, що з'єднують v з вершинами дерева А. (Якщо таких ребер немає, вв...
