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

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

Після того, як з теорією розібралися, перейдемо до розгляду delphi-проекту. Отже, після запуску програми, на екрані появиться форма наступного вигляду.

Пошук в ширину на delphi
Головне вікно проекту “Побудова дерева обходу в ширину для неорієнтованого графа”

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

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

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

Пошук в ширину на delphi
Неорієнтований граф

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

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

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

Пошук в ширину на delphi
Побудова дерева обходу в ширину

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

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

Залишити коментар

Your email address will not be published. Required fields are marked *

*