Алгоритм Косараджу
Алгоритм Косараджу (англ. kosaraju algorithm) — алгоритм для знаходження компонент сильної зв’язності орієнтованого графа. Ахо, Хопкрофт і Ульман приписують його до неоприлюдненого паперу Косараджу від 1978. Він використовує факт, що транспонований граф (той самий граф з оберненими напрямками ребер) має ті самі компоненти сильної зв'язності, що й початковий граф.
Алгоритм Косараджу працює так:
- Нехай G орієнтований граф і S порожній стек.
- Допоки S не містить всі вершини:
- Вибрати довільну вершину v не з S. Виконати пошук в глибину від v. По завершені пошуку в глибину для кожної вершини u, заштовхуємо u на S.
- Обернути всі ребра для отримання транспонованого графа.
- Доки S непорожній (містить вершину в порядку завершення, на верхівці стека — останнє завершення пошуку в глибину):
- Виштовхнути вершину v з S. Виконати пошук в глибину від v. Набір відвіданих вершин дасть компоненту сильної зв'язності, що містить v; записати це і видалити всі ці вершини з графа G і стека S. Так само можна використати пошук в ширину.
![](http://upload.wikimedia.org/wikipedia/uk/d/dd/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BE%D1%81%D0%B0%D1%80%D0%B0%D0%B4%D0%B6%D1%83_-_%D1%87%D0%B0%D1%81_%D0%B7%D0%B0%D0%B2%D0%B5%D1%80%D1%88%D0%B5%D0%BD%D0%BD%D1%8F_%D0%B2_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D0%B0%D1%85.png)
Розглянемо дві суміжні компоненти сильної зв'язності в G (зображення праворуч). Нехай f(v) — порядок завершення для вершини v в DFS-циклі. Тоді:
Доведення послуговується фактом, що мета-граф (ущільнений граф) такий, в якому всі компоненти сильної зв'язності стягнуті до однієї вершини є ациклічним.
Наслідок: найбільше значення f матиме в компоненті-джерелі (англ. source SCC), тобто вершина лежатиме на верхівці стека.
![](http://upload.wikimedia.org/wikipedia/uk/thumb/1/17/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BE%D1%81%D0%B0%D1%80%D0%B0%D0%B4%D0%B6%D1%83_-_%D0%B4%D0%BB%D1%8F_%D0%BB%D0%B5%D0%BC%D0%B8.png/220px-%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BE%D1%81%D0%B0%D1%80%D0%B0%D0%B4%D0%B6%D1%83_-_%D0%B4%D0%BB%D1%8F_%D0%BB%D0%B5%D0%BC%D0%B8.png)
Якщо на вході граф описаний за допомогою списком суміжності[en], алгоритм виконує два повних обходи графа, отже виконується за Θ(V+E) (лінійний) час, який є оптимальним, бо збігається з нижньою межею (кожен алгоритм повинен обійти всі вершини і ребра). Це концептуально найпростіший ефективний алгоритм, але не настільки швидкий як алгоритм Тарджана і алгоритм компонент сильної зв'язності по шляхах, які виконують лише один обхід графа.
Якщо граф представлено через матрицю суміжності, алгоритм потребує час Ο(V2).
- Опис і доведення алгоритму Косараджу [Архівовано 19 листопада 2011 у Wayback Machine.] (англ.)
- Добра математика, погана математика: Обчислення компонент сильної зв'язності (англ.)
- Java код на AlgoWiki.net (англ.)
|
![]() | Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її. |