Почему алгоритм Косарайю считается одним из самых эффективных алгоритмов для анализа графов?

Алгоритм Косарайю считается одним из самых эффективных алгоритмов для анализа графов, потому что он обеспечивает поиск сильных компонент связности графа за линейное время и память. ru.wikipedia.org ru.ruwiki.ru

Метод состоит из двух процедур поиска в глубину, подвергнутых незначительным изменениям, в результате время его выполнения пропорционально V² в случае насыщенных графов и V + E в случае разреженных графов (если графы представлены в виде списков смежных вершин). ru.wikipedia.org

Для графов, содержащих 100 вершин, этот алгоритм работает в 100 раз быстрее примитивного алгоритма, а для 1000 вершин — в 1000 раз быстрее, что позволяет решать подобные задачи для графов с миллионами вершин. intuit.ru