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

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

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

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

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

Читати далі

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

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

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

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

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

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

Читати далі

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

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

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

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

У загальному випадку, коли ми перейшли в будь-яку вершину графа, в нашому випадку це вершина , виникають два варіанти можливих дій:

Читати далі