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

Question

Я читаю Введение в алгоритмы. В 22.5 Сильно связанный компонент алгоритм STRONGLY-CONNECTED-COMPONENT(G) определяется как:

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

Если я изменю алогрит, просто используя G, не вычисляя транспонирование G. Также рассмотрим вершины в порядке увеличения uf(обратный порядок топологической сортировки):

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

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

Answer 1

Ваш вопрос на самом деле упражнение 22.5-3 в книге. Контрпример к правильности вашего альтернативного алгоритма приведен здесь: http://sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf

Предложение профессора Бэкона не работает. В качестве примера предположим, что наш граф находится на трех вершинах {1, 2, 3} и состоит из ребер (2, 1),(2, 3),(3, 2). Затем мы должны получить {2, 3} и {1} в качестве наших SCC. Тем не менее, возможный DFS, начинающийся с 2, может исследовать 3 до 1, это будет означать, что время финиша 15 из 3 меньше, чем 1 и 2. Это означает, что когда мы впервые выполняем DFS, начиная с 3. Тем не менее, начало DFS на 3 сможет добраться до всех остальных вершин. Это означает, что алгоритм вернет, что весь граф является одним SCC, даже если это явно не так, поскольку нет ни пути от 1 до 2, ни от 1 до 3.

Мое объяснение неудачи альтернативного алгоритма состоит в том, что для заданной вершины v в сильно связной компоненте C, если f(v) максимально, f(C) должно быть максимальным, но если f(v) минимально, чем f (В) не может быть минимальным.

Answer 2

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

Если вы ищете доказательство алгоритма, я уверен, что вы найдете его. Это может быть не самым простым для понимания, но проверьте этот источник, например: Правильность алгоритма для поиска сильно связанных компонентов