Я пытаюсь самостоятельно изучить теорию графов и теперь пытаюсь понять, как найти SCC на графике. Я прочитал несколько разных вопросов/ответов о SO (например, 1, 2, 3, 4, 5, 6, 7, 8), но я не могу найти его с полным пошаговым примером, которым я мог бы следовать.
Согласно CORMEN (Введение в алгоритмы), один из методов:
- Вызов DFS (G) для вычисления времени окончания f [u] для каждой вершины u
- Вычислить транспонирование (G)
- Вызовите DFS (Transpose (G)), но в основном цикле DFS рассмотрите вершины в порядке убывания f [u] (как вычислено на шаге 1)
- Выведите вершины каждого дерева в лесу глубины первого шага 3 как отдельный сильный компонент связи
Обратите внимание на следующий график (вопрос 3.4 из здесь. Я нашел несколько решений здесь и здесь, но я пытаюсь это сломать и понять сам.)
Шаг 1: Вызов DFS (G) для вычисления времени окончания f [u] для каждой вершины u
Запуск DFS, начиная с вершины A:
Обратите внимание, что RED-текст отформатирован как [Pre-Vist, Post-Visit]
Шаг 2: Вычислить транспонирование (G)
Шаг 3. Вызовите DFS (Transpose (G)), но в основном цикле DFS рассмотрите вершины в порядке убывания f [u] (как вычислено на шаге 1)
Хорошо, поэтому вершины в порядке убывания значений после посещения (окончания):
{E, B, A, H, G, I, C, D, F, J}
Итак, на этом этапе мы запускаем DFS на G ^ T, но начинаем с каждой вершины из приведенного выше списка:
- DFS (E): {E}
- DFS (B): {B}
- DFS (A): {A}
- DFS (H): {H, I, G}
- DFS (G): удалить из списка, поскольку он уже посещен
- DFS (I): удалить из списка, поскольку он уже посещен
- DFS (C): {C, J, F, D}
- DFS (J): удалить из списка, поскольку он уже посещен
- DFS (F): удалить из списка, поскольку он уже посещен
- DFS (D): удалить из списка, поскольку он уже посещен
Шаг 4: Выведите вершины каждого дерева в лесу глубины на шаге 3 как отдельный сильный компонент связи.
Итак, у нас есть пять сильно связанных компонент: {E}, {B}, {A}, {H, I, G}, {C, J, F, D}
