Терминологические вопросы:
Вы говорите о топологическом порядке, но топологический порядок существует тогда и только тогда, когда граф является DAG (направленным ациклическим). Если вы хотите работать только с группами доступности баз данных, у вас уже есть SCC (сильно связанные компоненты), поскольку каждая вершина является компонентом для себя. Если вы хотите найти SCC на ориентированных графах, вам нужно изменить топологический порядок на время окончания DFS . Книга CLRS упоминает только время окончания f[u]:
- Вызовите DFS (G ^ T), но в главном цикле DFS рассмотрите вершины в порядке убывания f [u] ...
Переформулировка вашего вопроса:
Неправильно ли искать сильно связанные компоненты в исходном графе с учетом вершин в порядке увеличения времени окончания f[u]?
Ответ:
Да, это неправильно.
Контрпример: рассмотрим следующий график:
, который содержит два компонента C и C'. Если вы запустите первую DFS (начиная с узла u), вы получите один из двух следующих списков в порядке возрастания к концу времени:
DFS список 1: {v,w',w,u}
DFS список 2: {w',v,w,u}
На самом деле вы спрашиваете, можете ли вы обрабатывать эти списки с самого начала на исходном графике. Если вы выберете первый список, вы извлечете компонент C' с помощью поиска DFS, начиная с узла v, а затем компонент C с помощью поиска DFS, начиная с узла w'. Но если вы выберете второй список и запустите DFS с узла w' на исходном графике, вы получите только один компонент (весь график), что неправильно.
Обратите внимание, что алгоритм Косараю работает в обоих случаях, так как он начинается с конца списка (узел u в обоих случаях) и извлекает компонент C посредством поиска DFS на обращенном графике. Компонент C' будет извлечен позже, когда мы достигнем узла v в списке.