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