Компоненты сильной связности с алгоритмом Косарайю
Выполните DFS исходного графа для получения порядка завершения, транспонируйте граф и снова выполните DFS в обратном порядке завершения, чтобы найти компоненты сильной связности
«Компоненты сильной связности с алгоритмом Косарайю» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Определение сильно связных компонент
Сильно связная компонента (SCC) ориентированного графа — это максимальное множество вершин, такое что из каждой вершины множества существует путь в любую другую вершину этого множества. Например, если вершины A, B, C образуют цикл (A→B→C→A), все они входят в одну SCC. Одна вершина без петли в себя образует собственную SCC. SCC раскрывают циклическую структуру ориентированного графа.
Алгоритм Kosaraju: два прохода DFS
Алгоритм Kosaraju находит все SCC за O(V + E), используя два прохода DFS. Проход 1: выполните DFS на исходном графе и помещайте вершины в стек в порядке завершения (постпорядке). Проход 2: выполните DFS на транспонированном (обращённом) графе, обрабатывая вершины в обратном порядке завершения (извлекая их из стека). Каждое дерево DFS во втором проходе представляет одну SCC.
Почему работает алгоритм Kosaraju
В первом проходе SCC, дерево DFS которой завершается последней, не имеет исходящих рёбер к другим SCC — это SCC-сток в конденсации DAG. В транспонированном графе у этой SCC нет входящих рёбер от других SCC, поэтому DFS из неё во втором проходе остаётся внутри этой SCC. Каждый следующий DFS во втором проходе также остаётся внутри собственной SCC, поскольку все рёбра между SCC обращены и ведут обратно к уже посещённым SCC.
Проход 1: построение порядка завершения
Выполните DFS на исходном графе и помещайте каждую вершину в стек после завершения её обработки (в постпорядке). На этом проходе нас не интересуют компоненты — важен только порядок завершения. Последняя завершившаяся вершина будет находиться в SCC-источнике конденсации DAG.
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u) # reversed edges
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs1(nxt)
finish_stack.append(node) # push after all neighbours done
for i in range(n):
if i not in visited:
dfs1(i)
return finish_stack, rev_graphПроход 2: DFS на транспонированном графе
Извлекайте вершины из стека завершения (начиная с наибольшего времени завершения) и выполняйте DFS на транспонированном графе. Каждый DFS из непосещённой вершины обнаруживает ровно одну SCC. Пометьте все вершины, достигнутые во время этого DFS, как принадлежащие одной и той же компоненте.
from collections import defaultdict
def kosaraju_full(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited: dfs1(nxt)
finish_stack.append(node)
for i in range(n):
if i not in visited: dfs1(i)
visited.clear()
sccs = []
def dfs2(node, component):
visited.add(node)
component.append(node)
for nxt in rev_graph[node]:
if nxt not in visited: dfs2(nxt, component)
while finish_stack:
node = finish_stack.pop()
if node not in visited:
component = []
dfs2(node, component)
sccs.append(component)
return sccs
# Graph with SCCs: {0,1,2} and {3}
edges = [(0,1),(1,2),(2,0),(1,3)]
print(kosaraju_full(4, edges)) # [[3], [0,2,1]] or similarТранспонирование графа
Транспонированный граф обращает каждое ребро: если в исходном графе есть u → v, то в транспонированном есть v → u. Транспонирование сохраняет SCC: если A и B находятся в одной SCC исходного графа, они останутся в одной SCC транспонированного графа, поскольку все пути обращаются, но по-прежнему соединяют вершины. Построение транспонированного графа во время чтения входных данных, как показано выше, позволяет избежать отдельного шага транспонирования.
Итеративная версия для больших графов
Для больших графов заменяйте рекурсивный DFS на итеративный DFS с явным стеком, чтобы избежать ограничения Python на глубину рекурсии. Итеративная версия помещает вершины в стек, обрабатывает их и поддерживает отдельный маркер «возврата» для имитации обхода в постфиксном порядке.
def dfs1_iterative(start, graph, visited, finish_stack):
stack = [(start, iter(graph[start]))]
visited.add(start)
while stack:
node, neighbours = stack[-1]
try:
nxt = next(neighbours)
if nxt not in visited:
visited.add(nxt)
stack.append((nxt, iter(graph[nxt])))
except StopIteration:
stack.pop()
finish_stack.append(node)
print('Iterative DFS for large graphs avoids recursion limit')Алгоритм Тарьяна: альтернативный способ поиска SCC
Алгоритм Тарьяна находит SCC за один проход DFS, тогда как алгоритм Косарайю использует два прохода. Он поддерживает стек вершин и присваивает каждой вершине время обнаружения и значение нижней ссылки. Когда время обнаружения вершины совпадает с её значением нижней ссылки, эта вершина является корнем SCC. Алгоритм Тарьяна немного сложнее реализовать, но он позволяет не строить транспонированный граф. Оба алгоритма имеют сложность O(V + E).
Применение SCC
SCC используются в следующих задачах: (1) оптимизация компилятора — выявление взаимно рекурсивных функций; (2) анализ социальных сетей — поиск тесно связанных сообществ; (3) задача 2-SAT — определение выполнимости дизъюнктов из двух литералов; (4) обход веб-страниц — выявление кластеров страниц с большим количеством взаимных ссылок; (5) конденсация DAG — после нахождения SCC конденсация графа становится DAG, что позволяет выполнять топологический анализ циклических графов.
Конденсация DAG
Конденсация ориентированного графа сворачивает каждую SCC в одну вершину и добавляет ребро между двумя сверхвершинами, если между соответствующими им SCC существует ребро. Результат всегда является DAG — на нём можно выполнить топологическую сортировку. Это позволяет применять к произвольным ориентированным графам алгоритмы, работающие только с DAG, например DP, выполняя их над конденсацией.
def build_condensation(n, edges, sccs):
# Assign each node to its SCC index
scc_id = [0] * n
for idx, component in enumerate(sccs):
for node in component:
scc_id[node] = idx
# Build condensation edges
condensation_edges = set()
for u, v in edges:
su, sv = scc_id[u], scc_id[v]
if su != sv:
condensation_edges.add((su, sv))
return list(condensation_edges)
edges = [(0,1),(1,2),(2,0),(1,3)]
sccs = [[3],[0,1,2]]
print(build_condensation(4, edges, sccs)) # [(0,1)] or [(1,0)]Число SCC и свойства графа
Число SCC в ориентированном графе показывает его циклическую структуру. В DAG имеется n SCC, поскольку каждая вершина образует отдельную SCC. В сильно связном графе ровно 1 SCC. В общем случае после свёртки SCC образуют DAG — конденсацию. Если у конденсации есть единственный источник (вершина с входящей степенью 0) и единственный сток (вершина с исходящей степенью 0), выполняются определённые свойства связности. Эти свойства проверяются в задачах о достижимости после добавления минимального числа рёбер.
Быстрая проверка
Проверьте своё понимание концепций «Структуры данных и алгоритмы — подготовка к собеседованиям по программированию» из этого урока.
Итоги урока
В этом уроке вы узнали, что SCC — это максимальные множества, в которых из каждой вершины достижима любая другая, алгоритм Косарайю использует два прохода DFS — сначала по исходному графу для определения порядка завершения, затем по транспонированному графу, а конденсацию любого ориентированного графа можно представить как DAG и использовать для дальнейшего анализа. Далее вы создадите структуры данных TrieNode для операций insert, search и работы с префиксами.
Часто задаваемые вопросы
Урок «Компоненты сильной связности с алгоритмом Косарайю» бесплатный?
Да — полный текст урока «Компоненты сильной связности с алгоритмом Косарайю» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Компоненты сильной связности с алгоритмом Косарайю»?
Выполните DFS исходного графа для получения порядка завершения, транспонируйте граф и снова выполните DFS в обратном порядке завершения, чтобы найти компоненты сильной связности Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Компоненты сильной связности с алгоритмом Косарайю»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Алгоритм Кана: топологическая сортировка с помощью BFS
- Топологическая сортировка DFS в порядке постобхода
- Расписание курсов I и II
- Компоненты сильной связности с алгоритмом Косарайю