Теоретичні відомості

Лабораторна робота № 5

Тема:Побудова остового дерева мінімальної вартості для поміченого графа за

алгоритмом Пріма.

Мета:Навчитись будувати остове дерево мінімальної вартості для поміченого

графа, використовуючи алгоритм Пріма .

Теоретичні відомості

Нехай маємо зв’язаний граф G=(V,E) з множиною вершин V={1, 2, .., n} і функцією вартості с, визначеній на множині ребер Е. В алгоритмі Пріма (Primm) побудова остового дерева мінімальної вартості для графа G починається з графа Т = (V, Ø), який складається тільки з n вершин графа G і не має ребер. Таким чином, кожна вершина є зв’язаною (сама із собою) компонентою. В процесі виконання алгоритму ми маємо набір зв’язаних компонент, поступово об’єднуючи деякі формуємо остове дерево.

При побудові зв’язаних, поступово зростаючих компонентів почергово перевіряються ребра з множини Е в порядку зростання їхньої вартості. Якщо чергове ребро зв’язує дві вершини з різних компонентів, тоді воно додається в граф Т. Якщо це ребро зв’язує дві вершини з однієї компоненти, тоді воно відкидається, так як його додавання в зв’язану компоненту, що є вільним деревом, веде до утворення циклу. Коли всі вершини графу G будуть належати одній компоненті, побудова остового дерева мінімальної вартості Т для цього графа закінчується.

Цей алгоритм можна реалізувати, використовуючи множини ( для вершин та ребер) і оператори. Перш за все, необхідна множина ребер Е, до якої можна було б послідовно застосовувати послідовно оператор DELETEMIN для відбору ребер в порядку зростання їхньої вартості. Тому множину ребер доцільно представити у вигляді черги з пріоритетами і використовувати для неї частково впорядковане дерево в якості структури даних. Необхідно також підтримувати набір С зв’язаних компонент, для чого можна використовувати наступні оператори:

1. Оператор MERGE(A,B,C) об’єднує компоненти А і В з набору С і результат об’єднання розміщує або в А, або у В.

2. Функція FIND(υ,C) повертає ім’я тої компоненти з набору С, яка містить вершину υ.

3. Оператор INITIAL(A,υ,C) створює у наборі С нову компоненту з іменем А, яка містить тільки одну вершину υ.

В будь-якому випадку алгоритм Пріма може бути виконаний за час О(е loge).

⇐ Предыдущая 2 3 4 5 6 7 8 91011 Следующая ⇒