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