# Декомпозиция Tarjan: компоненты сильной связности, мосты, точки сочленения и топологическая сортировка

Введите список рёбер (a b / a -> b, с весом) или списки смежности (a: b c): итеративный алгоритм Тарьяна (1972) и двухпроходный Косарайю взаимно проверяют разложение на компоненты сильной связности; вывод — точки сочленения и мосты, DAG конденсации с топологией Кана, отчёт о циклах и обходы BFS/DFS с ограничением глубины.

> Каноническая страница: https://elysiatools.com/ru/tools/tarjan-scc-tarjan-bridge-and-strongly-connected-components-topological-order-graph-decomposer

- **Категория:** Development

- **Ключевые слова:** Тарьян, компоненты сильной связности, Косарайю, точки сочленения, мосты, конденсация, топологическая сортировка, поиск циклов

## Обзор

SCC Тарьяна реализована итеративно с явным стеком (массивы disc/low, сбор при опустошении); Косарайю сортирует по времени завершения и собирает на обращённом графе — результаты должны совпадать покомпонентно (взаимная проверка). Мосты и точки сочленения определяются low-link на неориентированном представлении: low[v] > disc[u] ⟹ мост; корень с ≥2 поддеревьями или low[v] ≥ disc[u] ⟹ точка сочленения. Конденсация строит DAG компонентов, Кана даёт топологию; полный топологический порядок существует только для ациклического графа (узлы на циклах = SCC размера > 1 ∪ петли). BFS по слоям и DFS с явным стеком ограничены maxDepth. Сложность O(V+E).

## Входные данные

- **Граф (список рёбер или смежности, по одному в строке)** (textarea): a -> b b -> c c -> a d -> c
- **Ориентированный граф** (checkbox)
- **Стартовая вершина** (text): a
- **Максимальная глубина** (number): 4

## Когда использовать

- Для поиска циклических зависимостей и изолированных сильно связных подсистем в ориентированных графах.
- При анализе уязвимостей сетевых топологий и выявлении критических узлов (точек сочленения) и связей (мостов).
- Для построения корректного порядка выполнения задач в графах зависимостей через топологическую сортировку конденсации.
- Для генерации поуровневых обходов BFS или DFS с ограниченной глубиной от заданной стартовой вершины.

## Как это работает

- Инструмент принимает список рёбер (`a -> b` или `a b`) или список смежности (`a: b c`) и строит внутреннее представление графа.
- Итеративный алгоритм Тарьяна и алгоритм Косарайю вычисляют компоненты сильной связности (SCC) и выполняют взаимную сверку результатов.
- Через low-link значения на неориентированной проекции определяются мосты и точки сочленения (шарниры).
- Строится конденсационный ациклический граф (DAG), вычисляется топологический порядок по Кану и выполняются обходы BFS/DFS с учётом лимита maxDepth.

## Сценарии использования

- Анализ архитектуры микросервисов и сборщиков пакетов для выявления циклических импортов и зависимостей.
- Аудит надежности физических и логических сетей для поиска критических линий связи (мостов) и ключевых маршрутизаторов.
- Обучение и отладка алгоритмов теории графов с получением подробных отчётов по обходам и разбиению на компоненты.

## Частые вопросы

### В каком формате можно передавать граф на вход?

Поддерживается построчный ввод списка рёбер (`a -> b`, `a b` с опциональным весом) или списков смежности (`a: b c d`).

### Зачем запускаются одновременно алгоритмы Тарьяна и Косарайю?

Два независимых алгоритма осуществляют взаимную проверку вычисления компонент сильной связности, гарантируя корректность разложения.

### Как определяются мосты и точки сочленения?

Они находятся через массив глубин disc и low-link значений: мост при low[v] > disc[u], а точка сочленения при low[v] >= disc[u] либо для корня с двумя и более ветвями.

### Можно ли получить топологический порядок, если в графе есть циклы?

Для исходного графа с циклами полный порядок невозможен, но инструмент строит DAG конденсации и упорядочивает сами компоненты алгоритмом Кана.

### За что отвечают параметры startNode и maxDepth?

Они задают начальную вершину и максимальный уровень погружения для построения диагностических обходов BFS и DFS.

## Связанные инструменты

- [Визуализатор Cron-выражений](https://elysiatools.com/ru/tools/cron-expression-visualizer): Разбирает cron-расписания, проверяет синтаксис standard cron или Quartz и визуализирует будущие запуски на таймлайне и сгруппированном календаре
- [Синхронизатор палитры Tailwind](https://elysiatools.com/ru/tools/tailwind-color-palette-sync): Введите HEX, выберите схему именования (шкала 50–950 / одно имя / вложенность) — генерирует фрагмент theme.extend.colors для tailwind.config.ts с уровнями WCAG AA/AAA. Тёмная тема опциональна.
- [Объяснитель выражений Cron](https://elysiatools.com/ru/tools/cron-expression-explainer): Разбирает cron-выражение (5/6 полей или Quartz) в описание на естественном языке, разбивает по полям и выводит следующие N запусков в любой зоне IANA, с ИИ-объяснением
- [Симулятор cron-задач](https://elysiatools.com/ru/tools/cron-job-simulator): Моделирует будущие запуски одного или двух 5-польных cron-выражений, показывая пересечения и слишком частые интервалы.
- [Тестер мутаций API-контракта](https://elysiatools.com/ru/tools/api-contract-mutation-tester): Применяет семантические мутации к полям OpenAPI и при необходимости отправляет их на реальный backend для проверки защитной валидации
- [Хирург битых строк CSV](https://elysiatools.com/ru/tools/csv-malformed-row-surgeon): Поэлементно (хирургически) исправляет битые строки CSV: неэкранированные (случайные) кавычки, смешанные разделители (таб/точка с запятой/запятая в одном файле), заголовки с BOM, переводы строк CRLF/CR и лишние пустые строки. Хирург парсит терпимо, показывает построчный красно-зелёный diff каждой правки (до → после, с пометкой причины), перечисляет строки, принятые без изменений, и выводит очищенный CSV. Дополнительный ИИ-ремонт может перепроверить подозрительные строки после детерминированного прохода. Он дополняет Валидатор CSV (который лишь сообщает о проблемах), реально исправляя повреждённые строки.
- [Визуализатор потока OAuth 2.0 / OIDC с кодом авторизации и PKCE](https://elysiatools.com/ru/tools/oauth-oidc-authorization-code-pkce-flow-visualizer): Сквозная симуляция потока кода авторизации с PKCE: генерация verifier/challenge, URL авторизации, обмен токенами, чек-лист проверки ID Token и демо атаки перехвата.
- [Конструктор art direction для responsive Picture / srcset](https://elysiatools.com/ru/tools/responsive-picture-srcset-art-direction-builder): Генерирует полную разметку с art-direction-кропами: элементы на каждый брейкпоинт, кандидаты 1x/2x или w-дескрипторы по шаблону {w}, опциональные слои AVIF/WebP, работа с sizes, width/height против CLS, варианты HTML и JSX и lint-заметки по спецификации.

## Примеры

- [FLAC Аудио Образцы Без Авторских Прав](https://elysiatools.com/ru/samples/flac-samples): Коллекция аудио FLAC без потерь для тестирования и разработки, включая звуки природы и медитативную музыку
- [WAV Аудио Образцы Без Авторских Прав](https://elysiatools.com/ru/samples/wav-samples): Коллекция аудио WAV без сжатия для тестирования и разработки, включая звуки природы и медитативную музыку
- [Примеры Обработки Изображений Android Java](https://elysiatools.com/ru/samples/android-image-processing-java): Примеры обработки изображений Android Java включая чтение/сохранение, масштабирование и преобразование формата
- [Примеры Обработки Изображений Android Kotlin](https://elysiatools.com/ru/samples/android-image-processing-kotlin): Примеры обработки изображений Android Kotlin включая чтение/сохранение, масштабирование и преобразование формата