Использование обхода в глубину для поиска компонент сильной связности — различия между версиями
(→Пример реализации) |
м (rollbackEdits.php mass rollback) |
||
(не показано 59 промежуточных версий 10 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
− | |||
==Алгоритм== | ==Алгоритм== | ||
− | + | [[Файл: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> |
− | Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа | + | #Выполнить поиск в глубину в <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 | |
− | color[v] = 1 | + | '''for''' (v, u) '''in''' E |
− | for ( | + | '''if''' '''not''' visited[u] |
− | + | dfs1(G[v][u]) | |
− | if | + | Добавляем вершину v в конец списка ord |
− | |||
− | |||
− | ord | ||
− | |||
− | + | '''function''' dfs2(v): | |
− | + | component[v] = col | |
− | component[v] = col | + | '''for''' (v, u) '''in''' E |
− | for ( | + | '''if''' (вершина u еще не находится ни в какой компоненте) |
− | + | dfs2(H[v][u]) | |
− | if ( | ||
− | dfs2( | ||
− | |||
− | |||
− | + | '''function''' main(): | |
− | + | считываем исходные данные, формируем массивы G и H | |
− | + | '''for''' u '''in''' V | |
− | for | + | '''if''' '''not''' visited[u] |
− | + | dfs1(u) | |
− | if | + | col = 1 |
− | + | '''for''' (по всем вершинам u списка ord[] в обратном порядке) | |
− | + | '''if''' (вершина u не находится ни в какой компоненте) | |
− | col = 1 | + | dfs2(u) |
− | for ( | + | col++ |
− | |||
− | if ( | ||
− | dfs2( | ||
− | |||
− | |||
− | + | ==Источники информации== | |
+ | * Р.Седжвик. "Фундаментальные алгоритмы на С++. Алгоритмы на графах" - СПб, ДиаСофтЮП, 2002 | ||
+ | * [http://e-maxx.ru/algo/strong_connected_components MAXimal :: algo :: Поиск компонент сильной связности, построение конденсации графа] | ||
+ | * [http://rain.ifmo.ru/cat/view.php/vis/graph-general/scc-2008/| Визуализация поиска компонент сильной связности] | ||
+ | [[Категория: Алгоритмы и структуры данных]] | ||
+ | [[Категория: Обход в глубину]] |
Текущая версия на 19:35, 4 сентября 2022
Содержание
Алгоритм
Компоненты сильной связности в графе можно найти с помощью поиска в глубину в 3 этапа:
- Построить граф с обратными (инвертированными) рёбрами
- Выполнить в поиск в глубину и найти — время окончания обработки вершины
- Выполнить поиск в глубину в , перебирая вершины во внешнем цикле в порядке убывания
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа
Так как компоненты сильной связности и графа совпадают, то первый поиск в глубину для нахождения можно выполнить на графе , а второй — на .
Доказательство корректности алгоритма
Теорема: |
Вершины и взаимно достижимы после выполнения алгоритма они принадлежат одному дереву обхода в глубину. |
Доказательство: |
Если вершины и были взаимно достижимы в графе , то на третьем этапе будет найден путь из одной вершины в другую, это означает, что по окончанию алгоритма обе вершины лежат в одном поддереве.
|
Время работы алгоритма
- Для того, чтобы инвертировать все ребра в графе, представленном в виде списка потребуется действий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования.
- Количество ребер в инвертированном равно количеству ребер в изначальном графе, поэтому поиск в глубину будет работать за
- Поиск в глубину в исходном графе выполняется за .
В итоге получаем, что время работы алгоритма
.Псевдокод
Пусть
— исходный граф, —инвертированный граф. В массиве будем хранить номера вершин в порядке окончания обработки поиском в глубину в графе . В результате получаем массив , который каждой вершине сопоставляет номер её компоненты.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
- MAXimal :: algo :: Поиск компонент сильной связности, построение конденсации графа
- Визуализация поиска компонент сильной связности