Что делать, если я не использую транспонирование G при вычислении сильно связанных компонентов?

Question

Я читаю Введение в алгоритмы. В 22,5 Сильно подсоединенного компонента, алгоритм НАСТОЯТЕЛЬНО ВКЛЮЧЕНИЯ-КОМПОНЕНТ (G), определяется следующим образом:

1. Вызов ДФС (G), чтобы вычислить отделочные раз UF для каждой вершины и
2. Вычислить G транспонирование
3. вызова DFS (G transpose), но в основном цикле DFS, рассмотрим вершины в порядке убывания uf (как вычислено в строке 1)
4. Выведите вершины каждого дерева в лесу глубины, образованном в строке 3, как отдельный сильно соединенный компонент

Если я изменяю алографию только с помощью G, не вычисляя G транспонирование. Кроме того, рассмотреть вершины в порядке возрастания UF (обратный порядок топологической сортировки):

1. Вызов DFS (G), чтобы вычислить отделочные раз UF для каждой вершины и
2. вызова DFS (G), но в основном петля ДПП, рассмотрит вершину в порядке возрастания UF (вычисленной в строке 1)
3. выходе вершина каждого дерева в глубине первого леса формируется в строке 2

Почему этот алгоритм не так?

Answer 1

Вершины в сильно соединенной компоненте, определенными, связаны друг с другом (по пути, не обязательно прямым ребром). если вы сделаете первый вызов DFS на вершине X, вы узнаете, «какие вершины X связаны с» (X -> N). Чтобы убедиться, что все эти вершины соединены с X (N -> X) и поэтому проверяют сильную связность, вам нужно пересечь края в обратных направлениях. Самый простой способ сделать это - транспонирование графика.

Если вы ищете доказательство алгоритма, я уверен, что вы найдете его. Это, возможно, не так просто понять, но проверьте этот источник, например: Correctness of the algorithm for finding strongly connected components