Можно ли сгенерировать время окончания алгоритма Косараджу из исходного графика, а не из обратного графика?

Question

В алгоритме Косараджу время окончания генерируется из обращенного графика. Затем сильно связанные компоненты обнаруживаются из исходного графа, выполняя DFS, начиная с самого большого до самого низкого времени окончания, созданного ранее.

Можно ли сгенерировать время окончания алгоритма Косараджу из исходного графика? Тогда можно ли обнаружить сильно связанные компоненты, выполнив DFS, начиная с самого низкого времени окончания до самого большого времени окончания?

Мне кажется, что так и было, но это только моя догадка.

Answer 1

Нет, этот подход не обязательно сработает. Рассмотрим следующий график:

        A ---> C
 ^ |
 | |
 | v
  B

Давайте попробуем запустить предложенный вами алгоритм. Мы начнем запускать DFS с узла A, и всякий раз, когда у нас будет выбор, какой узел посетить следующим, мы выберем первый в алфавитном порядке. ДФС будет выглядеть так:

• Начать изучение А.
  • Начните изучать Б.
    • Завершите изучение Б.
  • Начните изучать С.
    • Завершите изучение C.
• Закончить изучение А.

Это дает нам время окончания как B, C, A.

Если мы теперь запустим поиск в глубину на исходном графе, двигаясь в порядке окончания времени, наша первая поиск в глубину будет из узла B. Это найдет узлы A, B и C, и поэтому мы придем к неверному выводу, что {A, B, C} — сильносвязный компонент графа, хотя SCC здесь на самом деле {A, B} и C.

Мы могли бы тогда спросить - почему это не работает? То есть, что такого особенного в движении задним ходом? Ответ заключается в том, что если мы запустим DFS и запишем время завершения узлов, то первый посещенный узел в каждом SCC будет иметь последнее время окончания всех узлов в SCC. Вот почему самый последний узел, который мы находим в упорядочении, должен быть, например, в исходном SCC. С другой стороны, не гарантируется, что время завершения других узлов в SCC будет иметь какие-либо особые свойства. (Вот как я нашел этот граф — я построил его так, чтобы первый узел, который завершится в одном из SCC, был бы упорядочен перед узлом в одном из SCC приемника).

Answer 2

Вкратце алгоритм Косараджу таков:

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

Таким образом, если шаг 1 пропущен, нерабочий пример можно упростить до графа с двумя узлами: .

Пропустите 1-й шаг. Начните с B, обратный порядок сообщений: B, A, поэтому DFS на исходном графике с использованием порядка дает один SCC, что неверно.

При этом используя тот же графикA <-- B, полностью правильный алгоритм (даже если стартовать с «неудобного» узла B):

1. реверс: А --> Б;
2. обратный почтовый заказ A, B;
3. DFS на исходном графе с использованием порядка дает два SCC (что правильно).

Конечно, тот же результат (два SCC) вы получите, если начнете первый шаг алгоритма с узла A. Это работает, поскольку на втором шаге вы получаете тот же порядок: A, B.