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

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

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

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

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

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

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

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

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

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

2 коментаря

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

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

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

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

*