Loading AI tools
Из Википедии, свободной энциклопедии
Ориентированный граф (орграф) называется сильно связным (англ. strongly connected), если любые две его вершины s и t сильно связны, то есть если существует ориентированный путь из в и одновременно ориентированный путь из в
Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы. Областью сильной связности называется множество вершин компонентов сильной связности.
Орграф, не принадлежащий к классу сильно связных графов, содержит некоторый набор сильно связных компонент, и некоторый набор ориентированных рёбер, идущих от одной компоненты к другой.
Любая вершина орграфа сильно связна сама с собой.
Простейший алгоритм решения задачи о поиске сильно связных компонент в орграфе работает следующим образом:
Очевидно основное время работы данного алгоритма занимает транзитивное замыкание.
Также существует три алгоритма, решающих данную задачу за линейное время, то есть в V раз быстрее, чем приведённый выше алгоритм. Это алгоритмы Косарайю, поиска компонент сильной связности с двумя стеками и Тарьяна.
На рисунке изображён орграф, для которого показаны все три компоненты сильной связности (закрашенные области, обведённые пунктиром).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.