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