Знаходження компонент сильної зв'язності орієнтованого графа

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

Орієнтований граф та його компоненти сильної зв'язності

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

Зв'язки між компонентами сильної зв'язності, зазвичай, зображаються шляхом створення конденсації графа . Відмітимо, що конденсацією орієнтованого графа називається граф, побудований наступним чином: набори вершин, що утворюють одну компоненту сильної зв'язності вихідного графа, зливаються в одну вершину конденсації . З вершини  у вершину конденсації є ребро тоді і тільки тоді, коли в графі  є ребро, що веде з деякої вершини компоненти зв'язності у деяку вершину компоненти зв'язності . Конденсація орієнтованого графа представлена ​​на вказаному вище рисунку у вигляді кіл зображених пунктирною лінією. Тобто, вершини вихідного графа, що утворюють одну компоненту сильної зв'язності, зливаються в одну вершину. Вершини  — в другу. І вершини і  — в третю та четверту відповідно. Ребра , і також відображені в конденсації, оскільки з'єднують вершини різних компонент сильної зв'язності.

Зауваження: в конденсації не може бути циклів, оскільки якби існував цикл, то всі компоненти сильної зв'язності, що входять в цей цикл, утворювали б одну компоненту сильної зв'язності.

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

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

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

Знаходження компонент сильної зв'язності графа — приклад:

Використовуючи розглянутий вище алгоритм, знайти компоненти сильної зв'язності для орієнтованого графа наступного вигляду:

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

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

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

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

Далі, шляхом заміни орієнтації всіх ребер заданого графа на протилежні, будуємо для нього трансповований граф. Після цього, запускаємо другий пошук в глибину, здійснюючи, при цьому, обхід  вершини відповідно до послідовності , починаючи з кінця. При цьому, вершина номер «4» складає перше піддерево пошуку, вершина «5» — друге, вершина «1» — третє, вершина «2» — четверте і вершини «6» та «3» — п'яте та шосте відповідно.

Дерево обходу в глибину транспонованого орієнтованого графа

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

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