Зміст
Введення
1 Алгоритм Краскала
1.1 Опис алгоритму Краскала
1.2 Псевдокод алгоритму
1.3 Блок-схема алгоритму
1.4 Складність алгоритму
2. Алгоритм Прима
2.1 Опис алгоритму Прима
2.2 Псевдокод алгоритму
2.3 Блок-схема алгоритму
2.4 Код програми
2.5 Оцінка складності
Висновок
Список використаних джерел
Введення
Об'єктом дослідження курсової роботи стала реалізація алгоритму Краскали.
Цілями роботи були:
) ознайомлення з алгоритмом Краскали, його історією;
) реалізація алгоритму, для побудови мінімального кістяка;
) аналіз трудомісткості алгоритму;
) тестування алгоритму.
Мінімальним остовне деревом (МОД) зв'язкового зваженого графа називається його зв'язний підграф, що складається з усіх вершин вихідного дерева і деяких його ребер, причому сума ваг ребер максимально можлива. Якщо вихідний граф незв'язний, то описувану нижче процедуру можна застосовувати по черзі до кожної його компоненті зв'язності, отримуючи тим самим мінімальні остовне дерева для цих компонент. p align="justify"> Алгоритм Краскала (або алгоритм Крускала) - алгоритм побудови мінімального отовность дерева зваженого зв'язного неорієнтованого графа. Алгоритм вперше описаний Джзефом Крускалом в 1956 році.
Алгоритм Краскала може будувати дерево одночасно для декількох компонент зв'язності, які в процесі вирішення об'єднуються в одне пов'язане дерево.
Повний граф задається списком ребер. Перед роботою список ребер сортується за зростанням довжини. На кожному кроці проглядається список ребер, починаючи з ребра, наступного за що увійшов до рішення на попередньому кроці, і до споруджуваного Піддерево приєднують то ребро, яка не утворює циклу з ребрами, вже включеними в рішення. p align="justify"> Задача про знаходження мінімального кістяка часто зустрічається в подібній постановці: є n міст, через які можна прокласти маршрут так , щоб можна було дістатися з будь-якого міста в будь-який інший (безпосередньо або через інші міста). Потрібно знайти такий маршрут, щоб вартість проїзду була максимальною.
На практиці алгоритм Краскали застосуються в роботі авіаліній при знаходженні найменшого повітряного дорозі з одного пункту призначення в інший.
Алгоритм Прима - алгоритм побудови мінімального кістяка зваженого зв'язного неорієнтовано...
