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

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

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

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

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

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

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

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

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

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

Зауваження: виходячи з того, що побудоване дерево обходу в глибину для орієнтованого графа складається крім ребер дерева та зворотних ребер також і з прямих та поперечних ребер, кожне з яких, в програмі, прорисовується своїм кольором, то задля того, щоб користувач мав змогу ідентифікувати до якого з типів відноситься то чи інше ребро в правому верхньому куті delphi-компонента TImage виводиться прямокутна область з відповідними підказками («колір ребра — тип ребра»).

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

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

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