Изменения

Данная задачи решается [[Файл: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'' достижима из ''r''</tex> и <tex>t</tex>, значит время выхода из чего следуетнее при первом обходе в глубину больше, что в обратном графе ''r'' достижима чем время выхода из ''вершин <tex>s''</tex> и <tex>t</tex>. Но ''Из этого мы получаем 2 случая:##Обе эти вершины были достижимы из <tex>r'' имеет большее время окончания обработки f[r] </tex> f[s], из чего следует что в обратном инвертированном графе существует путь из ''. А это означает взаимную достижимость вершин <tex>s</tex> и <tex>r</tex> и взаимную достижимость вершин <tex>r'' в ''</tex> и <tex>t</tex>. А складывая пути мы получаем взаимную достижимость вершин <tex>s''</tex> и <tex>t</tex>. Тогда ##Хотя бы одна не достижима из <tex>r</tex> в исходном инвертированном графе существуют пути как из ''s'' в ''r'', так например <tex>t</tex>. Значит и <tex>r</tex> была не достижима из ''r'' <tex>t</tex> в ''s''инвертированном графе, т.е. ''так как время выхода <tex>r'' и ''s'' сильно связаны</tex> - больше . Те же рассуждения доказываютЗначит между этими вершинами нет пути, но последнего быть не может, потому что ''<tex>t'' и ''</tex> была достижима из <tex>r'' сильно связаны</tex> по пункту 1).  Значит, из чего следует случая 2.1 и не существования случая 2.2 получаем, что ''вершины <tex>s</tex> и <tex>t'' и ''s'' также сильно связаны</tex> взаимно достижимы в обоих графах.}} ==Пример реализацииВремя работы алгоритма== vector#Для того, чтобы инвертировать все ребра в графе, представленном в виде списка потребуется <tex>O(V + E)</tex> действий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования.#Количество ребер в инвертированном равно количеству ребер в изначальном графе, поэтому поиск в глубину будет работать за <vectortex>O(V + E)<int/tex>#Поиск в глубину в исходном графе выполняется за <tex> gO(V + E)</tex>.В итоге получаем, g1; что время работы алгоритма <tex>O(V + E)</tex>. ==Псевдокод==Пусть <tex>G</g хранит tex> — исходный граф в виде списка смежностей, g1 - обратный vector<inttex>H</tex> —инвертированный граф. В массиве <tex> color, ord, component; <//цвет вершины, список tex> будем хранить номера вершин в порядке окончания обработкипоиском в глубину в графе <tex>G</tex>. В результате получаем массив <tex>component</tex>, номер компоненты, к который относиться вершина int col; //каждой вершине сопоставляет номер текущей её компоненты.

void dfs'''function''' dfs1(int & v) : //первый поиск в глубину, определяющий порядок обхода { color[v] = 1; '''for ''' (unsigned i = 0; i < g[v].size(, u); ++i) {'''in''' E '''if (color''' '''not''' visited[g[vu][i]] == 0) dfsdfs1(gG[v][iu]); } Добавляем вершину v в конец списка ord.push_back(v); }

void '''function''' dfs2(int & v) //второй поиск в глубину, выявляет компоненты сильной связности в графе {: component[v] = col; '''for ''' (unsigned i = 0; i < g1[v].size(); i ++ , u) {'''in''' E '''if ''' (component[g1[v][i]] == 0вершина u еще не находится ни в какой компоненте) dfs2(g1H[v][iu]); } }

int '''function''' main() {: ... //считываем исходные данные, формируем массивы g G и g1H '''for (int i = 1; i <= n; ++i) ''' u '''in''' V //формируем массив ord[] { '''if (color''' '''not''' visited[iu] == 0) dfsdfs1(iu); } col = 1; '''for ''' (int i = по всем вершинам u списка ord.size(); i > 0; --i) //ищем компоненты связности, вызывая вершины [] в обратном порядке { //от сохранённого в ord[], что соответствует уменьшению времени конца обработки f[]) '''if ''' (component[ord[i - 1]] == 0вершина u не находится ни в какой компоненте) dfs2(ord[i - 1]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/| Визуализация поиска компонент сильной связности][[Категория: Алгоритмы и структуры данных]][[Категория: Обход в component[iглубину]] имеем номер компоненты, к которой принадлежит вершина ''i''