Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала

Міністерство освіти і науки України

Сумський Державний Університет

Курсова робота

з дисципліни

«Теорія алгоритмів та математична логіка»

На тему

«Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала»

Виконав студент

факультету ЕлІТ групи ІН-83

Горбатенко О. О.

Перевірив Кузіков Б. О.

Суми 2010

Завдання роботи

При виконанні ОДЗ необхідно реалізувати алгоритми Прима та Крускала побудови остового дерева у графі, та протестувати її на тестовому графі наведеному у завданнях до ОДЗ згідно вашого варіанту. У пояснювальній записці до ОДЗ повинно бути викладено наступне:

• Вступ. Короткі відомості про поняття остового дерева;

• Завдання роботи, Включаючи тестовий приклад графу, згідно варіанта;

• Алгоритм Прима:

◦ короткі відомості про алгоритм та асимптотичну оцінку його швидкодії, спосіб представлення графу та його обґрунтування (10%);

◦ остове дерево, отримане за допомогою алгоритму (5%);

◦ фактичні параметри швидкодії (кількість порівнянь) для тестового прикладу (10%);

◦ оцінку швидкодії реалізованого варіанта алгоритму (10%).

• Алгоритм Крускала:

◦ короткі відомості про алгоритм та асимптотичну оцінку його швидкодії, спосіб представлення графу та його обґрунтування(10%);

◦ остове дерево, отримане за допомогою алгоритму (5%);

◦ фактичні параметри швидкодії (кількість порівнянь) для тестового прикладу (10%);

◦ оцінку швидкодії реалізованого варіанта алгоритму (10%).

• Порівняння алгортимів, контрольні приклади:

◦ висновок що до умов, коли доцільно використовувати той чи інший алгоритм (10%)

◦ довільний граф (10 або більше вершин), на якому алгоритм Прима дає перевагу, навести фактичні параметри швидкодії (10%);

◦ довільний граф (10 або більше вершин), на якому алгоритм Крускала дає перевагу, навести фактичні параметри швидкодії (10%).

Поставлене завдання: маючи на вході граф G, одержати на виході його остовне дерево мінімальної вартості, використати алгоритми Крускала й Прима. Порівняти використовувані алгоритми.

Вступ

Нехай G = (V, Е) — зв'язний граф, у якому кожне ребро (u,v ) позначено числом c(u, v), що називається вартістю ребра. Остовним деревом графа G називається вільне дерево, що містить всі вершини V графа G. Вартість остовного дерева обчислюється як сума вартостей всіх ребер, що входять у це дерево.

Типове застосування остовних дерев мінімальної вартості можна знайти при розробці комунікаційних мереж. Тут вершини графа представляють міста, ребра - можливі комунікаційні лінії між містами, а вартість ребер відповідає вартості комунікаційних ліній. У цьому випадку остовне дерево мінімальної вартості представляє комунікаційну мережу, що поєднує всі міста комунікаційними лініями мінімальної вартості.

Існують різні методи побудови остовних дерев мінімальної вартості. Багато хто з них ґрунтуються на наступній властивості остовних дерев мінімальної вартості. Нехай G = (V, Е) — зв'язний граф із заданою функцією вартості, що задана на множині ребер. Позначимо через U підмножину вершин V. Якщо (і, v) — таке ребро найменшої вартості, що й належить U і v належить V U, тоді для графа G існує остовное дерево мінімальної вартості, що містить ребро (і, v).

Існують два популярних алгоритми побудови остовного дерева мінімальної вартості для позначеного графа G = (V, Е), основані на описаній властивості: Прима й Крускала. Обидва алгоритми відповідають «жадібній» стратегії: на кожному кроці вибирається локально найкращий варіант.

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

Алгоритм Прима поступово будує шуканий мінімальний остов, додаючи до нього по одному ребру на кожному кроці (Це означає, що алгоритм Прима є жадібним. Більш того, справедливість алгоритму Прима легко встановлюється в рамках теорії матроідов.). На початку роботи алгоритму результуюче дерево складається з однієї вершини (її можна вибирати довільно). Алгоритм складається з N-1 ітерації, на кожній з яких до дерева додається рівно одне ребро, не порушує властивості дерева (тобто один кінець додається ребра належить дереву, а інший - не належить). Ключовий момент - з усіх таких ребер кожен раз вибирається ребро з мінімальною вагою. Така реалізація працює за O (MN).

Покращена реалізація буде виконуватися помітно швидше - за O (M log N + N2).

Для цього ми відсортуємо всі ребра в списках суміжності кожної вершини по збільшенню ваги (буде потрібно O (M log M) = O (M log N)). Крім того, для кожної вершини заведемо покажчик, який вказує на перше доступне ребро в її списку суміжності. Спочатку всі покажчики вказують на початку списків, тобто рівні 0. На i-ої ітерації алгоритму Прима ми перебираємо всі вершини, і вибираємо найменше за вагою ребро серед доступних. Оскільки всі ребра вже відсортовані за вагою, а покажчики вказують на перші доступні ребра, то вибір найменшого ребра здійсниться за O (N). Тепер нам слід оновити покажчики, оскільки деякі з них вказують на що стали недоступними ребра (обидва кінці яких опинилися всередині дерева), тобто зрушити деякі з них праворуч. Проте, оскільки у всіх списках суміжності в сумі 2 * M елементів, а покажчики зсуваються тільки вправо, то виходить, що на підтр

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать