Мітки: пошук в глибину

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

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

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

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

Перевірка орієнтованого графа на наявність циклів

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

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

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

Перевірка орієнтованого графа на наявність циклів

Нехай при обході даного графа методом пошуку в глибину вершині присвоєно найменшу глибину обходу серед усіх вершин, що становлять цикл. Розглянемо ребро , що належить цьому циклу. Оскільки вершина входить в цикл, то вона повинна бути нащадком вершини в побудованому дереві обходу в глибину. Тому ребро не може бути поперечним. Але, виходячи з того, що глибина обходу вершини більша за глибину обходу вершини то ребро також не може бути ні ребром дерева ні прямим ребром. Звідси, ребро є зворотним, як показано на малюнку, що міститься вище.

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

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

Пошук в глибину

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

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

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

Пошук точок сполучення в неорієнтованому графі засобами delphi

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

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

Головне вікно проекту “Пошук точок сполучення в зв’язному неорієнтованому графі”

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

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

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

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

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