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

Зміст

Введення

1. Постановка завдання

2. Методи вирішення даної проблеми

3. Опис алгоритму Краскала

4. Приклад роботи алгоритму Краскала

5. Код програми

6. Огляд роботи програми

Висновок

Список використаної літератури

Введення

Мінімальним Остовним деревом (МОД) зв'язкового зваженого графа називається його зв'язний подграф, що складається з усіх вершин вихідного дерева і деяких його ребер, причому сума ваг ребер максимально можлива. Якщо вихідний граф несвязен, то описувану нижче процедуру можна застосовувати по черзі до кожної його компоненті зв'язності, отримуючи тим самим мінімальні остовного дерева для цих компонент.

Задача про знаходження мінімального остовного дерева часто зустрічається в подібній постановці: є n міст, через які можна прокласти маршрут так, щоб можна було дістатися з будь-якого міста в будь-який інший (безпосередньо або через інші міста). Потрібно знайти такий маршрут, щоб вартість проїзду була максимальною.

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

Існує кілька алгоритмів для знаходження мінімального остовного дерева. Деякі найбільш відомі з них перераховані нижче:

В· Алгоритм Прима;

В· Алгоритм Краскала;

В· Алгоритм Борувкі.

1. Постановка завдання

Нехай є зв'язний неорієнтовані граф G, на ребрах якого задана вагова функція c (e). Зв'язний подграф графа G, що є деревом і містить всі його вершини, називають покриваючим деревом (spanning-tree) цього графа (іноді використовують термін остовне дерево або остов). Вагою остовного дерева будемо вважати суму ваг усіх його ребер. Тоді виникає задача про знаходження максимального покриває дерева, тобто такого, що його вага найбільший, або дорівнює вазі будь-якого з покриваючих дерев для даного графа. Будемо позначати найбільше покриває дерево графа G як MAX (G).

2. Методи вирішення даної проблеми

Остовним деревом графа називається дерево, що містить всі вершміни V графа. Вартість остовного дерева обчислюється як сума вартостей всіх ребер.

Ідея рішення:

Для остовного дерева вірно наступне властивість:

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

На цій властивості заснований алгоритм Прима. У цьому алгоритмі будується множина вершин U, з якого "Виростає" остовне дерево. Нехай V = {1,2,. n}. Спочатку U = {1}. На кожному кроці алгоритму знаходиться ребро найменшої вартості (u, v) таке, що u з U і v з V U, потім вершина v переноситься з безлічі V U в безліч U. Процес триває до тих пір, поки безліч U не стане рівним безлічі V.

Деталі реалізації:

Зручно вибрати уявлення у вигляді списку дуг.

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

Визначимо поняття каркаса більш формально. Якщо дана зв'язний неорієнтовані граф G = (V, E), то каркас (Також званий Остовним або стягивающим деревом) T = (V, E '), де E'ГЌE - це зв'язний граф без циклів. Іншими словами, каркас неорієнтованого графа G - це підграф графа G, дерево, містить всі вершини графа. Зрозуміло, що для того, щоб T мало той же набір вершин, що і зв'язний граф G, і щоб T не мало циклів, воно повинно містити рівно | V | -1 ребро.

Припустимо, що для кожного ребра eГЋE існує вагу w (e), причому таку вагу може виражати, наприклад, ціну, довжину або час, необхідний для проходу по ребру (у нашому прикладі - Довжину кабелю між будівлями). У зваженому графі вага подграфа - це сума ваг його ребер. Тоді каркас T максимальної ваги - це каркас G, в якому вага дерева максимальний щодо всіх остовних дерев G.

Якщо граф G незв'язний, він не може мати остовного дерева, але у нього є остовного ліс. Також можна змінити алгоритм знаходження остовного дерева максимальної ваги, щоб на виході отримувати мінімальний остовного ліс.

остовне дерево алгоритм Краскала

В алгоритмі Краскала використовується жадібний підхід до вирішення завдання, тобто в будь-який момент виконання даних алгоритмів існує безліч ребер E ', що представляє підмножину деякого мінімального остовного дерева графа G. На кожному кроці алгоритмів з решти ребер вибирається "найкращий" ребро, що має певні властивості, і додається до формованому каркасу максимальної ваги. Одним з важливих властивостей будь-якого ребра, додається до E ', є його безпека, тобто те, що оновлене безліч ребер E 'буде продовжувати представляти підмножина деякого мінімального остовного дерева.

3. Опис алгоритму Краскала

Алгоритм Краскала може будувати дерево одночасно для декількох компонент зв'язності, які в процесі вирішення об'єднуються в одне пов'язане дерево.

Повний граф задається списком ребер. Перед роботою список ребер сортується за зростанням довжини. На кожному кроці проглядається список ребер, починаючи з ребра, наступного за який увійшов в рішення на попередньому кроці, і до споруджуваного піддерево приєднують то ребро, яке не утворює циклу з ребрами, вже включеними в рішення.

Алгоритм складається з наступної послідовності дій:

1. Створюється список ребер R, що містить довжину ребра, номер вихідної вершини ребра (i), номер кінцевої вершини ребра (j), ознака включення даного ребра в дерево.

2. Даний список впорядковується в порядку зростання довжин ребер.

3. Проглядається список R і вибирається з нього ребро з максимальною довжиною, ще не включене в результуюче дерево і не утворить циклу з вже побудованими ребрами.

4. Якщо всі вершини включені в дерево і кількість ребер на одиницю менше кількості вершин, то алгоритм свою роботу закінчив. В іншому випадку здійснюється повернення до пункту 3.

Або в термінах теорії графів:

Дан граф з n вершинами; довжини ребер задані матрицею. Знайти остовне дерево максимальної довжини.

У задачі Прима-Краскала, яка не здається особливо простий, жадібний алгоритм дає точне оптимальне рішення.

Як відомо (Це легко довести по індукції), дерево з n вершинами має n-1 ребер. Виявляється, кожне ребро потрібно вибирати жадібно (лише б не виникали цикли). Тобто n-1 раз вибирати найкоротший ребро з ще не вибране ребро за умови, що воно не утворює циклу з вже обраними.

А як стежити, щоб нове ребро не утворювало циклу зі старими? Зробити це просто. До побудови дерева забарвимо кожну вершину i у відмінний від інших колір i. При виборі чергового ребра, наприклад (i, j), де i та j мають різні кольори, вершина j і все, пофарбовані в її колір (Тобто раніше з нею з'єднані) перефарбовуються в колір i. Таким чином, вибір вершин різного кольору забезпечує відсутність циклів. Після вибору n-1 ребер всі вершини отримують один колір.

Доведемо, що описаний алгоритм отримує в точно...сті максимальне рішення. Для доказу нам знадобиться дуже просте твердження:

Якщо до дерева додати ребро, то в дереві з'явиться цикл, що містить це ребро.

Дійсно, нехай додано ребро (u, v) - "додано" означає, що ребро - нове, що раніше його в дереві не було. Оскільки дерево є пов'язаною графом, то існує ланцюг C (u, ..., v) з декількох ребер, що з'єднує вершини u і v. Додавання ребра (u, v) замикає ланцюг, перетворюючи її в цикл.

Теорема . Алгоритм Прима-Краскала отримує максимальне остовне дерево .

Доказ . Результатом роботи алгоритму є набір з n-1 ребер. Вони не утворюють циклу, бо на кожному з n-1 кроків з'єднувалися вершини різного кольору, тобто раніше не пов'язані. Цей граф зв'язний, тому що після проведення 1-го ребра залишилося n-1 різних кольорів, ..., після проведення (n-1) - го ребра залишився один колір, тобто одна компонента зв'язності. Отже, отриманий набір ребер утворює зв'язний граф без циклів, що містить n-1 ребер і n вершин. Отже, граф є остовне дерево. Залишилося довести, що воно має мінімальну довжину. Нехай {,, ...,} ребра остовного дерева в тому порядку як їх вибирав алгоритм, тобто ≥. Припустимо для простоти докази, що всі ребра мережі мають різну довжину, тобто

>> ...> (1)

Якщо отримане дерево не максимально, то існує інше дерево, заданий набором з n-1 ребер {,, ...,}, таке що сума довжин більше суми довжин . З точністю до позначень

>> ...> (2)

Можливо =, = і т.д., але оскільки дерева різні, то в послідовностях (1) і (2) знайдеться місце, де ребра відрізняються. Нехай саме ліве таке місце - k, так, що В№. Оскільки вибиралося по алгоритму найбільшим з не утворюють циклу з ребрами,, ...,, то>. Тепер додамо до дерева (2) ребро . У ньому з'явиться цикл, що містить ребро і, може бути, якісь (або всі) ребра,, ...,, але вони самі не утворюють циклу, тому в циклі буде обов'язково ребро d з набору, ...,, причому d>. Викинемо з отриманого графа з одним циклом ребро d. Ми знову отримаємо дерево, але воно буде на d-коротше мінімального, що неможливо. Отримане протиріччя доводить теорему для мережі з усіма різними ребрами.

4. Приклад роботи алгоритму Краскала

Малюнок 1. Початковий граф

Малюнок 2. Максимальне остовне дерево.

В алгоритмі Краскала ми не зберігаємо масив used [N]. Замість цього ми будемо на кожній ітерації алгоритму перевіряти, чи належать кінці розглянутого ребра до різних компонентів зв'язності (і додавати ребро до каркаса, якщо це так).

Введемо лічильник int counter = 0. Нехай N - кількість вершин графа.

Впорядкуємо список ребер по зростанню ваги.

Якщо counter == N - 1, закінчимо виконання алгоритму.

Проходячи по списку ребер, знайдемо ребро (i, j) таке, що i та j належать різним компонентам зв'язності. Так як список впорядкований по зростанню ваги ребер, ми будемо вибирати ребро з максимальною вагою, що задовольняє умові.

Додамо це ребро в каркас, збільшимо на одиницю лічильник counter.

Перейдемо до кроку 2.

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

5. Код програми

// ---------------------------------------------

# include

# include

# include

// -------------------------------------------

typedef int * tint;// Покажчик на int

void main ()

{//int max = 100;// Максимальний вага ребра

int n;// кількість вершин

tint * G;// вихідний граф

tint * H;// матриця списку ребер з вагою

tint * K;/* матриця, яка зазначає належність

вершини компоненті */

tint * T;// матриця остовного дерева

tint * L;// список ребер з цінами мінімального дерева

// ----- введення графа

int max;

cout <<" Maximalno dopustimoe zna4enie vesa rebra = ";

cin>> max;

cout <<" n Vvedite 4ilo vershin: n ";

cin>> n;

G = new tint [n];

for (int i = 0; i

G [i] = new int [N];

cout <<" Vvedite nignij treugolnik matrici stoimosti: n ";

for (int i = 1; i

for (int j = 0; j

cin>> G [i] [J];

}

for (int i = 1; i

for (int j = 0; j

G [j] [i] = G [i] [j];

// --- виділення пам'яті для списку ребер ---

int kolreb = 0;

for (int i = 1; i

for (int j = 0; j

if (G [i] [j]

kolreb + +;

H = new tint [kolreb];

for (int i = 0; i

H [i] = new int [3];

// -------------------------------------------

int a = 0;

for (int i = 1; i

for (int j = 0; j

if (G [i] [j]

H [a] [0] = i +1;

H [a] [1] = j +1;

H [a] [2] = G [i] [J];

a + +;

}

cout <

// ---- сортування ребер по зростанню ваги

int f, d, s; ​​

for (int i = 0; i

for (int j = 0; j

if (H [j] [2]

f = H [j] [2];

H [j] [2] = H [j +1] [2];

H [j +1] [2] = f;

d = H [j] [0];

H [j] [0] = H [j +1] [0];

H [j +1] [0] = d;

s = H [j] [1];

H [j] [1] = H [j +1] [1];

H [j +1] [1] = s;

}

// вивід ребер відсортованих по зростання ваги

cout <<"Matrica dostigimosni otsortirovannoe po ubivaniuy: n ";

for (int i = 0; i

cout <";

cout <

cout <

cout <<" ";

}

for (int i = 0; i

H [i] [0] -;

H [i] [1] -;

}

// матриця для визначення компоненти

K = new tint [n];

for (int i = 0; i

K [i] = new int [2];

for (int i = 0; i

K [i] [0] = i;

K [i] [1] = 0;

}

// ---- матриця остовного дерева

T = new tint [n];

for (int i = 0; i

T [i] = new int [N];

for (int i = 0; i

for (int j = 0; j

T [i] [j] = 0;

//-приєднання першого ребра

T [H [0] [0]] [H [0] [1]] = H [0] [2];

T [H [0] [1]] [H [0] [0]] = H [0] [2];

K [H [0] [0]] [1] = 1;

K [H [0] [1]] [1] = 1;

// алгоритми з'єднання ребер без створення циклу:

int m = 2;// номер компоненти

for (int i = 1; i

if (K [H [i] [0]] [1]! = K [H [i] [1]] [1])

// якщо 2 вершини не з однієї компоненти

{

if (K [H [i] [0]] [1]> 0 && K [H [i] [1]] [1]> 0)

// якщо обидві вершини належать різним компоненті

{

for (int j = 0; j

if (K [H [i] [1]] [1] == K [j] [1])

K [j] [1] = K [H [I] [0]] [1];

K [H [i] [1]] [1] = K [H [i] [0]] [1];

T [H [i] [0]] [H [I] [1]] = H [i] [2];

T [H [i] [1]] [H [I] [0]] = H [i] [2];

}

if ((K [H [i] [0]] [1]> 0 && K [H [i] [1]] [1] == 0)

| | (K [H [i] [0]] [1] == 0 && K [H [i] [1]] [1]> 0))

// якщо одна вершина має компоненту а ін немає

{

if (K [H [i] [0]] [1]! = 0)

K [H [i] [1]] [1] = K [H [i] [0]] [1];...

if (K [H [i] [1]] [1]! = 0)

K [H [i] [0]] [1] = K [H [i] [1]] [1];

T [H [i] [0]] [H [I] [1]] = H [i] [2];

T [H [i] [1]] [H [I] [0]] = H [i] [2];

}

if (K [H [i] [0]] [1] == 0 && K [H [i] [1]] [1] == 0)

// якщо обидві вершини не мали компоненти

{

K [H [i] [0]] [1] = M;

K [H [i] [1]] [1] = M;

T [H [i] [0]] [H [I] [1]] = H [i] [2];

T [H [i] [1]] [H [i] [0]] = H [i] [2];

m + +;

}

}// кінець перевірки всіх ребер

// --- виділення пам'яті для списку ребер

kolreb = 0;

for (int i = 1; i

for (int j = 0; j

if (T [i] [j]

kolreb + +;

L = new tint [kolreb];

for (int i = 0; i

L [i] = new int [3];

// ------------------------------------------

// --- висновок ребер

cout <

a = 0;

for (int i = 1; i

for (int j = 0; j

if (T [i] [j]

L [a] [0] = i +1;

L [a] [1] = j +1;

L [a] [2] = T [i] [J];

a + +;

}

for (int i = 0; i

cout <";

cout <

cout <

}

int b = 0;

for (int i = 0; i

b + = L [i] [2];

cout <

getch ();

// return 0;

}

// --------------------------------------------- -----------------

6. Огляд роботи програми

Після виконання програми виводяться ребра максимальної ваги, і вартість остовного дерева.

Висновок

У курсовому проекті був розроблена програма, що реалізує алгоритм Краскала, пошук максимального остовного дерева.

Алгоритм Краскала дійсно знаходить остовного ліс максимальної ваги, оскільки він є приватним випадком алгоритму Радо - Едмондс для графічного матроіда, де незалежні безлічі - Ациклічні безлічі ребер.

Список використаної літератури

1. Рибаков Гліб. Мінімальні остовного дерева.

2. Архангельський А.Я., C + + Builder 6. Довідковий посібник.

3. Бєлов Теорія Графів, Москва, "Наука", 19 68.

4. Кузнєцов О.П., Адельсон-Бєльський Г.М. Дискретна математика для інженера. - М.: Вища , 1988.

5. rain. ifmo.ru