Изменения

Данная задачи решается [[Файл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны.<br>Синим цветом обозначен обод DFS по инвертированным ребрам]][[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связности]] в графе <tex>G</tex> можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в глубину ]] в 3 этапа:

#Выполнить в <tex>H</tex> поиск в глубину и найти <tex>f[u]</tex> - — время окончания обработки вершины <tex>u</tex>

Так как компоненты сильной связности <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>s</tex> и <tex>t</tex> были взаимно лежат в одном и том же дереве поиска в глубину на третьем этапе алгоритма. Значит, что они обе достижимы из корня <tex>r</tex> этого дерева. # Вершина <tex>r</tex> была рассмотрена вторым обходом в графе глубину раньше, чем <tex>s</tex> и <tex>Gt</tex>, то они будут взаимно значит время выхода из нее при первом обходе в глубину больше, чем время выхода из вершин <tex>s</tex> и <tex>t</tex>. Из этого мы получаем 2 случая:##Обе эти вершины были достижимы и из <tex>r</tex> в инвертированном графе . А это означает взаимную достижимость вершин <tex>s</tex> и <tex>r</tex> и взаимную достижимость вершин <tex>Hr</tex>. Рассмотрим дерево обхода в глубину графа и <tex>Ht</tex>. Поскольку вершины А складывая пути мы получаем взаимную достижимость вершин <tex>s</tex> и <tex>t</tex> взаимно достижимы, то очевидно, что .##Хотя бы одна не достижима из них окажется в поддереве другой. Без потери общности скажем, что вершина <tex>tr</tex> оказалась в поддереве вершины инвертированном графе, например <tex>st</tex>. Значит, время выхода из вершины и <tex>tr</tex> будет меньше, чем время выхода была не достижима из вершины <tex>st</tex>. Соответственнов инвертированном графе, во так как время третьего шага алгоритма вершина выхода <tex>sr</tex> будет рассмотрена раньше- больше . Значит между этими вершинами нет пути, но последнего быть не может, чем вершина потому что <tex>t</tex>, а значит, вершина была достижима из <tex>sr</tex> снова попадет в ее поддерево, и они окажутся в одной компоненте сильной связностипо пункту 1).

Рассмотрим корень <tex>r</tex> дерева второго обхода в глубину==Время работы алгоритма==#Для того, чтобы инвертировать все ребра в котором оказались вершины <tex>s</tex> и <tex>t</tex>. В графе <tex>G</tex> существует путь из <tex>r</tex> , представленном в виде списка потребуется <tex>s</tex> и в <tex>tO(V + E)</tex>действий. Рассмотрим теперь дерево обхода Для матричного представления графа <tex>H</tex>не нужно выполнять никакие действия для его инвертирования. То, что вершина <tex>r</tex> была рассмотрена вторым обходом #Количество ребер в глубину раньше, чем <tex>s</tex> и <tex>t</tex>, говорит нам о том, что время выхода из нее больше, чем время выхода из вершин <tex>s</tex> и <tex>t</tex>. Это может означать, что или обе эти вершины были достижимы из <tex>r</tex>, что означает их взаимную достижимость инвертированном равно количеству ребер в обоих графах, или что между <tex>r</tex> и этими вершинами вообще нет пути ни в одну сторонуизначальном графе, ни поэтому поиск в другую. Но последнего быть не может, так как эти вершины были достижимы из глубину будет работать за <tex>rO(V + E)</tex> #Поиск в графе <tex>G</tex>, а значит, вершина <tex>r</tex> достижима из них глубину в исходном графе выполняется за <tex>HO(V + E)</tex>. ЗначитВ итоге получаем, вершины что время работы алгоритма <tex>sO(V + E)</tex> и <tex>t</tex> взаимно достижимы в обоих графах.

==Пример реализацииПсевдокод== vectorПусть <vectortex>G<int/tex>— исходный граф, <tex> g, h; H<//g хранит tex> —инвертированный граф в виде списка смежностей, h - инвертированный 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[g[v]''' '''not''' visited[i]u] == 0) dfsdfs1(gG[v][iu]); } ord.push_back(v); //добавляем Добавляем вершину v в конец списка ord[] }

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

int '''function''' main() {: ... //считываем исходные данные, формируем массивы g G и hH '''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++; } } По окончании выполнения алгоритма в <tex>component[i]</tex> имеем номер компоненты, к которой принадлежит вершина <tex>i</tex>.

==ЛитератураИсточники информации==