Побудова мінімального кістяка в неорієнтованому графі використовуючи алгоритм Борувки

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

Ілюстрація роботи алгоритму Борувки

Ілюстрація роботи алгоритму Борувки

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

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

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

Уникнення неодназначностей при побудові мінімального кістяка

Уникнення неодназначностей при побудові мінімального кістяка

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

Знаходження дерева мінімальної вартості використовуючи алгоритм Борувки — приклад:

Використовуючи розглянутий алгоритм Борувки, знайти дерево мінімальної вартості для наступного неорієнтованого графа:

Алгоритм Борувки приклад

Неорієнтований граф задачі

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

Алгоритм Борувки - ітерація №1

Алгоритм Борувки - ітерація №1

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

Алгоритм Борувки - ітерація №2

Алгоритм Борувки - ітерація №2

Блок-схема алгоритму знаходження дерева мінімальної вартості використовуючи алгоритм Борувки

Алгоритм Борувки блок-схема

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар