Викиконспекты - Вклад участника [ru]

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

2016-01-04T15:29:34Z

213.24.126.177: /* Псевдокод */

==Алгоритм==
[[Файл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны. Синим цветом обозначен обод 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>. 
Так как компоненты сильной связности <tex>G</tex> и <tex>H</tex> графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй — на <tex>H</tex>.
 

==Доказательство корректности алгоритма==
{{Теорема
|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/| Визуализация поиска компонент сильной связности]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]

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

2016-01-04T14:42:27Z

213.24.126.177: /* Псевдокод */

==Алгоритм==
[[Файл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны. Синим цветом обозначен обод 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>. 
Так как компоненты сильной связности <tex>G</tex> и <tex>H</tex> графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй — на <tex>H</tex>.
 

==Доказательство корректности алгоритма==
{{Теорема
|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/| Визуализация поиска компонент сильной связности]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]