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

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

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

  1. Панель інструментів: містить чотири кнопки, три з яких призначені для побудови та редагування графа («Додати вершину», «Видалити вершину», «Видалити граф») і чеверта («Знайти дерево мінімальної вартості») — реалізує процедуру побудови мінімального кістятка за алгоритмом Борувки.
  2. Область графічного представлення: призначена для побудови та візуалізації неорієнтованого графа. Зупинимося на ній більш детально. Отже, для того, щоб намалювати вершини графа потрібно, в першу чергу, активізувати кнопку панелі задач «Додати вершину». Після цього, з допомогою лівої кнопки мишки розставляємо їх в області форми — «Граф». Також передбачено можливість переміщення вершини (для цього, необхідно натиснути лівою кнопкою мишки по необхідній вершині, після чого, перетягнути її в потрібне місце). Для видалення вершини активуємо одноіменну кнопку на панелі задач і натиснувши лівою кнопкою мишки по відповідній вершині, ми її видаляємо.
  3. Область представлення графа у вигляді матриці суміжності призначена для побудови неорієнтованого ребра та задання його відстані.
  4. Область виводу результатів: статусний рядок, який міститься в нижній частині форми та у якому дерево мінімальної вартості виводиться у вигляді списку ребер (відмітимо, що ребра, які формують мінімальний кістяк також підсвічуються зеленим кольором і у області «Граф»).

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

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

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

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

Побудова неорієнтованого ребра

Побудова неорієнтованого графа

Далі, скориставшись кнопкою «Знайти дерево мінімальної вартості» знаходимо мінімальний кістяк заданого графа.

Побудова дерева мінімальної вартості

Побудова дерева мінімальної вартості

Скачати delphi-проект Побудова мінімального кістяка використовуючи алгоритм Борувки.

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

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