Вы когда-нибудь задумывались, что влечет за собой этот алгоритм?
Алгоритм Корасаджу — это алгоритм линейного графа для нахождения сильносвязных компонентов ориентированного графа.
Он основан на идее, что если можно достичь вершины v, начиная с вершины u, то можно достичь вершины u, начиная с вершины v, и если это так, то можно сказать, что вершины u и v являются сильно связные — они находятся в сильно связном подграфе.
Он используется для нахождения компонентов сильной связности, это части ориентированного графа, в котором есть путь из каждой вершины в каждую другую вершину той же части.
Мы можем сделать только три шага, чтобы найти компоненты сильной связности.
1. Мы начинаем с создания пустого стека, мы можем сказать, что это «S», затем мы выполняем поиск в глубину (DFS) обход графа. При обходе DFS после того, как узел полностью покрыт, то есть нет других соседних соседей этого узла для посещения, только после этого мы вставляем этот узел в наш стек.
2. Во-вторых, мы меняем направления всех ребер на противоположные, чтобы получить транспонированный граф.
3. В-третьих, одну за другой вытолкнуть вершину из S, пока S не пуста. Будем говорить, что все выскочившие вершины — это «V». Если V не посещается, мы делаем DFS (v).
