В данной дипломной работе рассматривается метод нахождения компонент сильной связности SCC ориентированного графа. Компоненты сильной связности SCC – это подграфы (максимальные по включению) такие, что любые две вершины, принадлежащие подграфу, достижимы друг из друга. Задача на нахождение компонент встречалась в литературе и описана в книге А. Ахо, Д. Хопкрофта и Д. Ульмана «Структуры данных и алгоритмы».
Мне было поручено реализовать представленный в этой книге алгоритм Косарайю (1983 г.). Что и было сделано.
Алгоритм был написан на языке c++ и проверен на десятке примеров графов разной размерности.
Так как зависимость времени работы алгоритма асимптотически линейна
от размера графа (так утверждается в книге), ожидать большой трудоемкости при обработке графа большей размерности не следует.
