Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Курсовые обзорные » Алгоритми Краскала і Прима

Реферат Алгоритми Краскала і Прима





містить) процедура, починаюча з клітинки 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 Шукаємо ребро з'єднує безліч остовних і безліч залишилися і має найменшу вагу <...


Назад | сторінка 3 з 5 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Поняття алгоритму і його властивості. Блок-схема алгоритму. Технологія Ro ...
  • Реферат на тему: Графові моделі. Остов мінімальної ваги
  • Реферат на тему: Створення алгоритму пошуку високоінформативних діагностичних ознак захворюв ...
  • Реферат на тему: Дослідження алгоритму сортування методом прямого включення
  • Реферат на тему: Створення інформаційного ресурсу та реалізація алгоритму сортування даних