Изменения

==Постановка задачиАлгоритм==Дан [[ориентированный графФайл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны.<br>Синим цветом обозначен обод DFS по инвертированным ребрам]][[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связности]] ''''' в графе <tex>G'''''. Требуется </tex> можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в этом графе [httpглубину]] в 3 этапа:#Построить граф <tex>H</tex> с обратными (инвертированными) рёбрами #Выполнить в <tex>H</neerc.ifmo.rutex> поиск в глубину и найти <tex>f[u]</mediawikitex> — время окончания обработки вершины <tex>u</index.phptex>#Выполнить поиск в глубину в <tex>G</%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8tex>,_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D1%8B_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8#перебирая вершины во внешнем цикле в порядке убывания <tex>f[u]</tex>Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа <tex>G</tex>.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.B2.D1.8F.D0.B7.D0.BD.D0.BE.D1.81.D1.82.D1.8C <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>, то на третьем этапе будет найден путь из одной вершины в другую, это означает, что по окончанию алгоритма обе вершины лежат в одном поддереве.

==Алгоритм=={{Определение|definition=Дополнением или обратным к графу <tex>G\Leftarrow</tex> называется такой граф  # Вершины <tex>Hs</tex>, имеющий то же множество вершин, что и <tex>Gt</tex>, но лежат в котором две несовпадающие вершины смежны тогда одном и только тогдатом же дереве поиска в глубину на третьем этапе алгоритма. Значит, когда что они не смежны в обе достижимы из корня <tex>Gr</tex>}}Данная задачи решается с помощью поиска в глубину в 3 этапа:этого дерева. #Построить обратный граф#Выполнить в обратном графе поиск в глубину и найти Вершина <tex>f[u]r</tex> - время окончания обработки вершины была рассмотрена вторым обходом в глубину раньше, чем <tex>us</tex>#Выполнить поиск глубину в и <tex>Gt</tex>, перебирая вершины во внешнем цикле значит время выхода из нее при первом обходе в порядке убывания глубину больше, чем время выхода из вершин <tex>f[u]s</tex>Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа и <tex>Gt</tex>. Из этого мы получаем 2 случая:Так как компоненты сильной связности исходного и обратного графа совпадают, то первый поиск в глубину для нахождения ##Обе эти вершины были достижимы из <tex>f[u]r</tex> можно выполнить на в инвертированном графе <tex>G</tex>, а второй - на обратном.===Доказательство===Рассмотрим пару А это означает взаимную достижимость вершин <tex>s</tex> и <tex>tr</tex>.Если вершины и взаимную достижимость вершин <tex>sr</tex> и <tex>t</tex> взаимно достижимы, то они обязательно будут находиться в одном дереве поиска в глубину, поскольку, когда просматривается первая из них, вторая остаётся непосещённой и достижимой из первой и будет просмотрена, прежде чем завершится рекурсивный вызов из корня.Теперь докажем, что если А складывая пути мы получаем взаимную достижимость вершин <tex>s</tex> и <tex>t</tex> находятся в одном дереве поиска, то они являются сильно связанными. Пусть <tex>r</tex> - корень этого дерева. Тогда <tex>s</tex> ##Хотя бы одна не достижима из <tex>r</tex>, из чего следует, что в обратном инвертированном графе , например <tex>s</tex> достижима из <tex>st</tex>. Но Значит и <tex>r</tex> имеет большее время окончания обработки была не достижима из <tex>f[r]t</tex> > <tex>f[s]</tex>, из чего следует что в обратном инвертированном графе существует путь из , так как время выхода <tex>r</tex> в <tex>s</tex>- больше . Тогда в исходном графе существуют Значит между этими вершинами нет пути как из , но последнего быть не может, потому что <tex>st</tex> в была достижима из <tex>r</tex>по пункту 1).  Значит, так из случая 2.1 и из не существования случая 2.2 получаем, что вершины <tex>rs</tex> в и <tex>st</tex>взаимно достижимы в обоих графах.}} ==Время работы алгоритма==#Для того, чтобы инвертировать все ребра в графе, т.е. представленном в виде списка потребуется <tex>rO(V + E)</tex> и <tex>s</tex> сильно связаныдействий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования. Те же рассуждения доказывают#Количество ребер в инвертированном равно количеству ребер в изначальном графе, что поэтому поиск в глубину будет работать за <tex>tO(V + E)</tex> и #Поиск в глубину в исходном графе выполняется за <tex>rO(V + E)</tex> сильно связаны.В итоге получаем, из чего следует что время работы алгоритма <tex>t</tex> и <tex>sO(V + E)</tex> также сильно связаны.

==Пример реализацииПсевдокод== vectorПусть <vectortex>G<int/tex>— исходный граф, <tex> g, g1; H<//g хранит tex> —инвертированный граф в виде списка смежностей, g1 - обратный vector. В массиве <inttex> 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''