Компоненты сильной связности: Косарайю и Тарьян

Описание

Интерактивный разбор: https://grundyjs.ru/algorithms/strongly-connected-components/?utm_source=rutube&utm_medium=social&utm_campaign=strongly_connected_components&utm_content=horizontal

Компоненты сильной связности — группы вершин ориентированного графа, внутри которых из каждой вершины можно добраться до любой другой. Сравниваем алгоритмы Косарайю и Тарьяна на одном графе.

Косарайю делает два обхода: сначала записывает порядок выхода в исходном графе, затем разворачивает все стрелки и обходит граф в обратном порядке выхода. Тарьян использует один DFS, номера посещения, метки low и отдельный стек ещё не выделенных вершин. Этот стек отличается от текущего пути DFS.

По ребру в вершину из стека Тарьяна учитываем её номер посещения, а при возврате из дочерней ветки — её low. Когда после проверки исходящих рёбер low равна номеру вершины, снимаем вершины со стека до неё включительно: это одна готовая компонента.

В примере получаются {A, B, C}, {D, E} и {F, G}. Порядок выдачи у алгоритмов различается, состав групп совпадает. Добавьте ребро F → B в интерактивном примере и проверьте, сколько компонент останется.

На сайте можно выбирать готовые графы, менять вершины и рёбра, проходить шаги, делиться ссылкой и сохранять анимацию. Такты анимации и счётчики не сравнивают время работы алгоритмов.

Авторская озвучка, без музыки. Русские субтитры подготовлены отдельно.

#алгоритмы #Косарайю #Тарьян #графы #программирование