14
правок
Изменения
→Алгоритм
#Выполнить в обратном графе поиск в глубину и найти <tex>f[u]</tex> - время окончания обработки вершины <tex>u</tex>
#Выполнить поиск глубину в <tex>G</tex>, перебирая вершины во внешнем цикле в порядке убывания <tex>f[u]</tex>
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа <tex>G</tex><br>
Так как компоненты сильной связности исходного и обратного графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй - на обратном.
===Доказательство===
Рассмотрим пару вершин <tex>s</tex> и <tex>t</tex>.
Если вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы, то они обязательно будут находиться в одном дереве поиска в глубину, поскольку, когда просматривается первая из них, вторая остаётся непосещённой и достижимой из первой и будет просмотрена, прежде чем завершится рекурсивный вызов из корня.<br>
Теперь докажем, что если <tex>s</tex> и <tex>t</tex> находятся в одном дереве поиска, то они являются сильно связанными. Пусть <tex>r</tex> - корень этого дерева. Тогда <tex>s</tex> достижима из <tex>r</tex>, из чего следует, что в обратном графе <tex>s</tex> достижима из <tex>s</tex>. Но <tex>r</tex> имеет большее время окончания обработки <tex>f[r]</tex> > <tex>f[s]</tex>, из чего следует что в обратном графе существует путь из <tex>r</tex> в <tex>s</tex>. Тогда в исходном графе существуют пути как из <tex>s</tex> в <tex>r</tex>, так и из <tex>r</tex> в <tex>s</tex>, т.е. <tex>r</tex> и <tex>s</tex> сильно связаны. Те же рассуждения доказывают, что <tex>t</tex> и <tex>r</tex> сильно связаны, из чего следует что <tex>t</tex> и <tex>s</tex> также сильно связаны.
