-
Алгоритм Тарьяна применим к направленным графам и используется для поиска компонент сильной связности в графах, включая те, которые содержат циклы.
-
Топологическая сортировка применяется только к направленным ацикличным графам (DAG), и используется для упорядочивания вершин, чтобы можно было правильно выполнять зависимости между задачами.
1. Алгоритм Тарьяна для поиска компонент сильной связности
Описание: Алгоритм Тарьяна используется для поиска компонент сильной связности (SCC — Strongly Connected Components) в направленных графах. Сильная связность графа означает, что для каждой пары вершин в компоненте существует путь между ними в обоих направлениях. Граф делится на такие компоненты, которые являются максимальными по своему размеру и которые не могут быть объединены без потери сильной связности.
Шаги алгоритма:
-
Инициализируем пустые стеки и списки для отслеживания времени входа в вершины, а также текущие индексы вершин.
-
Обходим граф с использованием поиска в глубину (DFS).
-
Каждый раз, когда мы посещаем вершину, помечаем её индексом времени (номер, когда вершина была посещена), а также добавляем её в стек.
-
Когда посещена вся компонентная связность, можно по стеку извлечь её компоненты и пометить как одну компоненту сильной связности.
Алгоритмическая сложность:
- Время работы алгоритма — O(V + E), где V — количество вершин, E — количество рёбер в графе. Это объясняется тем, что каждая вершина и каждое ребро проходят через алгоритм только один раз.
Применение:
-
Составление планов задач с зависимостями.
-
Выявление циклов в графах и анализ взаимосвязанных компонентов.
2. Топологическая сортировка
Описание: Топологическая сортировка — это линейное упорядочивание вершин направленного ацикличного графа (DAG), такое что для каждого ребра (u, v) вершина u идёт перед вершиной v. Топологическая сортировка используется для задач, где необходимо выполнить действия в определённом порядке. Она широко применяется в задачах, таких как компиляция кода, управление зависимостями и планирование задач.
Шаги алгоритма:
-
Для каждой вершины графа считаем её входную степень (число рёбер, направленных в эту вершину).
-
Вначале выбираем все вершины с нулевой входной степенью и помещаем их в очередь.
-
Пока очередь не пуста:
-
Извлекаем вершину из очереди.
-
Для каждой вершины-соседа уменьшаем её входную степень. Если входная степень соседа становится равной нулю, добавляем его в очередь.
-
-
Продолжаем этот процесс до тех пор, пока не получим все вершины в порядке сортировки.
Алгоритмическая сложность:
- Время работы — O(V + E), где V — количество вершин, E — количество рёбер, так как каждая вершина и каждое ребро обрабатываются только один раз.
Применение:
-
Планирование задач, где существует зависимость.
-
Компоненты компиляторов.
-
Составление расписаний с учётом зависимости задач.
Сравнение алгоритмов
| Алгоритм | Тип графа | Время работы | Применение | Особенности |
|---|---|---|---|---|
| Алгоритм Тарьяна | Направленный граф | O(V + E) | Поиск компонент сильной связности | Работает с циклами и сильно связанными компонентами |
| Топологическая сортировка | Направленный ацикличный граф (DAG) | O(V + E) | Планирование задач, компиляция, анализ зависимостей | Работает только с DAG, обеспечивает упорядочение задач |