Введение 3
Графо-теоретические понятия 4
Связность, достижимость 5
Поиск в глубину 8
Алгоритм Косарайю 13
Реализация алгоритмов Габова и Тарьяна 17
Заключение 19
Список литературы
В ряде приложений важно уметь выделить в графе компоненты сильной связности.
Мне было поручено сделать обзор имеющихся алгоритмов анализа связности ориентированного графов.
В этом анализе большую роль играют понятия «шарниры» и «компоненты сильной связности». Грубо говоря, шарниры - это вершины, такие, что разделение графа в них делит граф на сильно-связные компоненты.
Мне нужно было выяснить, какие сейчас приняты методы выделения в графе сильно-связных компонент.
Оказалось, есть три известных популярных алгоритма, которые и описываются в этой работе. К сожалению, конкурировать с этими алгоритмами я не смогла.
Основное внимание в работе уделено алгоритму Косарайю.
Таким образом рассмотрели алгоритмы нахождения компонент сильной связности орграфа.
В литературе есть программы этих методов, построенных на популярном методе в глубину.
Алгоритмы настолько маленькие, что их оказалось возможным привести полностью.
