Просмотр исходного текста страницы Использование обхода в глубину для поиска компонент сильной связности

==Алгоритм==
[[Файл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны.<br>Синим цветом обозначен обод DFS по инвертированным ребрам]]
[[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связности]]  в графе <tex>G</tex> можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в глубину]] в 3 этапа:
#Построить граф <tex>H</tex> с обратными (инвертированными) рёбрами 
#Выполнить в <tex>H</tex> поиск в глубину и найти <tex>f[u]</tex> — время окончания обработки вершины <tex>u</tex>
#Выполнить поиск в глубину в <tex>G</tex>, перебирая вершины  во внешнем цикле в порядке убывания <tex>f[u]</tex>
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа <tex>G</tex>.<br>
Так как компоненты сильной связности <tex>G</tex> и <tex>H</tex> графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй — на <tex>H</tex>.
<br clear = "all">

==Доказательство корректности алгоритма==
{{Теорема
|statement=
Вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы <tex>\Leftrightarrow</tex> после выполнения алгоритма они принадлежат одному дереву обхода в глубину.
|proof=
<tex>\Rightarrow</tex>

Если вершины <tex>s</tex> и <tex>t</tex> были взаимно достижимы в графе <tex>G</tex>, то на третьем этапе будет найден путь из одной вершины в другую, это означает, что по окончанию алгоритма обе вершины лежат в одном поддереве.

<tex>\Leftarrow</tex>

# Вершины <tex>s</tex> и <tex>t</tex> лежат в одном и том же дереве поиска в глубину на третьем этапе алгоритма. Значит, что они обе достижимы из корня <tex>r</tex> этого дерева. 
# Вершина <tex>r</tex> была рассмотрена вторым обходом в глубину раньше, чем <tex>s</tex> и <tex>t</tex>, значит время выхода из нее при первом обходе в глубину больше, чем время выхода из вершин <tex>s</tex> и <tex>t</tex>. Из этого мы получаем 2 случая:
##Обе эти вершины были достижимы из <tex>r</tex> в инвертированном графе. А это означает взаимную  достижимость вершин <tex>s</tex> и <tex>r</tex> и взаимную достижимость вершин <tex>r</tex> и <tex>t</tex>. А складывая пути мы получаем взаимную достижимость вершин <tex>s</tex> и <tex>t</tex>.
##Хотя бы одна не достижима из <tex>r</tex> в инвертированном графе, например <tex>t</tex>. Значит и <tex>r</tex> была не достижима из <tex>t</tex> в инвертированном графе, так как время выхода <tex>r</tex> - больше . Значит между этими вершинами нет пути, но последнего быть не может, потому что <tex>t</tex> была достижима из <tex>r</tex> по пункту 1). 

Значит, из случая 2.1 и не существования случая 2.2 получаем, что вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы в обоих графах.
}}

==Время работы алгоритма==
#Для того, чтобы инвертировать все ребра в графе, представленном в виде списка потребуется <tex>O(V + E)</tex> действий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования.
#Количество ребер в инвертированном равно количеству ребер в изначальном графе, поэтому поиск в глубину будет работать за <tex>O(V + E)</tex> 
#Поиск в глубину в исходном графе выполняется за <tex>O(V + E)</tex>.
В итоге получаем, что время работы алгоритма <tex>O(V + E)</tex>.

==Псевдокод==
Пусть <tex>G</tex> — исходный граф, <tex>H</tex> —инвертированный граф. В массиве <tex>ord</tex> будем хранить номера вершин в порядке окончания обработки поиском в глубину в графе <tex>G</tex>. В результате получаем массив <tex>component</tex>, который каждой вершине сопоставляет номер её компоненты.
    
    '''function''' dfs1(v):                                          
        color[v] = 1
        '''for''' (v, u) '''in''' E
            '''if''' '''not''' visited[u]
                dfs1(G[v][u])
        Добавляем вершину v в конец списка ord
    
    '''function''' dfs2(v):                                          
        component[v] = col
        '''for''' (v, u) '''in''' E
            '''if''' (вершина u еще не находится ни в какой компоненте)                       
                dfs2(H[v][u])
    
    '''function''' main():
        считываем исходные данные, формируем массивы G и H
        '''for''' u '''in''' V                           
            '''if''' '''not''' visited[u]
                dfs1(u)
        col = 1
        '''for''' (по всем вершинам u списка ord[] в обратном порядке)                                                        
            '''if''' (вершина u не находится ни в какой компоненте)
                dfs2(u)
                col++

==Источники информации==
* Р.Седжвик. "Фундаментальные алгоритмы на С++. Алгоритмы на графах" - СПб, ДиаСофтЮП, 2002
* [http://e-maxx.ru/algo/strong_connected_components  MAXimal :: algo :: Поиск компонент сильной связности, построение конденсации графа]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/scc-2008/| Визуализация поиска компонент сильной связности]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]