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

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

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

poshuk_cykliv_ta_komponent_zvjaznosti_grafa12

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

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

Перевірка графа на зв'язність та ациклічність — приклад:

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

Пошук циклів та компонент звя'зності графа - приклад

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

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

poshuk_cykliv_ta_komponent_zvjaznosti_grafa111

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

Проаналізувавши отриманий результат бачимо, що для того, щоб всі вершини заданого графа були пройдені, необхідно здійснити три етапи алгоритму обходу в глибину. Тобто заданий граф не є зв'язним і складається з трьох компонент зв'язності , та .

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

Блок-схема алгоритму перевірки графа на ациклічність способом обходу в глибину

Блок-схема алгоритму перевірки графа на ациклічність способом обходу в ширину

Блок-схема алгоритму перевірки графа на зв'язність способом обходу в глибину

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар