Перевірка орієнтованого графа на ациклічність в середовищі програмування delphi

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

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

Вихідні дані програми — побудова дерева обходу в глибину та вивід у компонентів TMemo послідовності вершин орієнтованого циклу, якщо він існує.

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

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

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

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

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

Пошук циклів у орієнтованому графі

Скачати delphi-проект Перевірка орієнтованого графа на наявність циклів.

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

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

*