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