Побудова дерева обходу в глибину в середовищі програмування delphi

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

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

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

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

Пошук в глибину на delphi

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

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

Пошук в глибину на delphi

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

На наступному кроці, поєдняємо їх відповідними неорієнтованими ребрами.

Пошук в глибину на delphi

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

Далі, скориставшись кнопкою «Побудувати дерево обходу в гибину» визначаємомо порядок обходу вершин та ребра, які утворюють шукане дерево (виділені жирними лініями з заданим напрямком).

Пошук в глибину на delphi

Побудова дерева обходу в гибину

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

Скачати delphi-проект Побудова дерева обходу в гибину для неорієнтованого графа.

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

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