містить) процедура, починаюча з клітинки Parent [x], у якій зберігається номер безпосереднього предка елемента x; - функція, виконує об'єднання двох частин в одну.
1.3 Блок-схема алгоритму
На малюнку 1 представлена ​​загальна схема алгоритму.
алгоритм Краскала прим псевдокод
В
Рисунок 1 - Загальна схема
На малюнку 2 представлена ​​блок-схема алгоритму сортування вставками.
Рисунок 2 - Блок-схема алгоритму сортування вставками
На малюнку 3 представлена ​​блок-схема алгоритму Краскала
В
Рисунок 3 - Блок-схема алгоритму Краскала
1.4 Складність алгоритму
Складність цього алгоритму збігається зі складністю використовуваного алгоритму сортування, оскільки число операцій у циклі while лінійно за кількістю ребер. Тому складність алгоритму Крускала пошуку МОД дорівнює O (E og Е).
2. Алгоритм Прима
2.1 Опис алгоритму Прима
Опис.
Сам алгоритм має дуже простий вигляд. Шуканий мінімальний остов будується поступово, додаванням в нього ребер по одному. Спочатку остов покладається складається з єдиною вершини (її можна вибрати довільно). Потім вибирається ребро мінімальної ваги, що виходить з цієї вершини, і додається в мінімальний остов. Після цього остов містить вже дві вершини, і тепер шукається і додається ребро мінімальної ваги, що має один кінець в одній з двох обраних вершин, а інший - навпаки, у всіх інших, крім цих двох. І так далі, тобто щоразу шукається мінімальне по вазі ребро, один кінець якого - вже взята в остов вершина, а інший кінець - ще не взяти, і це ребро додається в остов (якщо таких ребер кілька, можна взяти будь-яке). Цей процес повторюється до тих пір, поки остов чи не стане містити всі вершини (або, що те ж саме, n-1 ребро). У підсумку буде побудований остов, який є мінімальним. Якщо граф був спочатку не зв'язний, то остов знайдений не буде (кількість вибраних ребер залишиться менше n-1). p align="justify"> Вхід: Зв'язний неорієнтовані граф G (V, E)
Вихід: Безліч T ребер мінімального кістяка
Алгоритм.
В· Безліч остовних вершин - вихідна вершини
В· Безліч залишилися - всі вершини за винятком вихідної
В· Поки безліч залишилися не порожньо:
o Шукаємо ребро з'єднує безліч остовних і безліч залишилися і має найменшу вагу <...
