Побудова мінімального кістятка за алгоритмом Борувки в середовищі програмування delphi

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

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

Читати повністю

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

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

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

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

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

Читати повністю