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

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

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

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

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

Читати повністю

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

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

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

Читати повністю