> 4 v 5 v 6 v 7 v 1 1111000v 2 1111000v 3 1111000v 4 1111000v 5 0000110v 6 0000110v 7 0000001
Аналізуючи матрицю взаімодостіжімості, знаходимо такі класи взаімодостіжімих вершин: {v 1 , v 2 , v 3 , v 4 }, {v 5 , v 6 }, {v 7 < span align = "justify">}. Сільносвязний компоненти орграфа представлені вище на рис. 3.18.
2. Послідовність виконання роботи
Отже, щоб перейти до реалізації даного алгоритму, необхідно розділити кожну фазу, позначену вище, на певну кількість кроків:
Дві вершини A, B орієнтованого графа називаються сильно, пов'язаними якщо є шляхи з A в B і з B в A. Ставлення сильної пов'язаності транцітівно, тобто якщо A сильно пов'язана з B, а B сильно пов'язана з C, то A сильно пов'язана з C.
Сильно зв'язного компонентою орієнтованого графа називають безліч вершин графа, в якому для будь-яких двох вершин є шляхи сиз першої в другу і з другої в першу.
Багато алгоритми, що працюють на орієнтованих графах починають свою роботу з виділення сильно связнихкомпонент: після цього завдання вирішується для кожної компоненти окремо, і рішення комбінуються.
Граф задається масивом зв'язків, що виходять з кожної вершини.
Для виділення сильно зв'язкових компонент використовують два пошуку в глибину.
-ий раз на вихідному графі, 2-ий на транспоновану (вихідний граф, в якому звернені всі дозволені напрямки).
- Connected - Components (G)
1. За допомогою DFS (G), для кожної вершини u, знайти час закінчення обробки - f [u]
2. Побудувати G T
