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