Использование обхода в глубину для поиска компонент сильной связности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Постановка задачи)
(Доказательство)
Строка 12: Строка 12:
 
Рассмотрим пару вершин <tex>s</tex> и <tex>t</tex>.
 
Рассмотрим пару вершин <tex>s</tex> и <tex>t</tex>.
 
Если вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы, то они обязательно будут находиться в одном дереве поиска в глубину, поскольку, когда просматривается первая из них, вторая остаётся непосещённой и достижимой из первой и будет просмотрена, прежде чем завершится рекурсивный вызов из корня.<br>
 
Если вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы, то они обязательно будут находиться в одном дереве поиска в глубину, поскольку, когда просматривается первая из них, вторая остаётся непосещённой и достижимой из первой и будет просмотрена, прежде чем завершится рекурсивный вызов из корня.<br>
Теперь докажем, что если <tex>s</tex> и <tex>t</tex> находятся в одном дереве поиска, то они являются сильно связанными. Пусть <tex>r</tex> - корень этого дерева. Тогда <tex>s</tex> достижима из <tex>r</tex>, из чего следует, что в инвертированном графе <tex>r</tex> достижима из <tex>s</tex>. Но <tex>r</tex> имеет большее время окончания обработки <tex>f[r]</tex> > <tex>f[s]</tex>, из чего следует что в инвертированном графе существует путь из <tex>r</tex> в <tex>s</tex>. Если бы его не существовало, то путь из <tex>s</tex> в <tex>r</tex> в инвертированном графе оставлял бы <tex>s</tex> с большим временем окончания обработки <tex>f[s]</tex>. Тогда в исходном графе существуют пути как из <tex>s</tex> в <tex>r</tex>, так и из <tex>r</tex> в <tex>s</tex>, т.е. <tex>r</tex> и <tex>s</tex> сильно связаны. Те же рассуждения доказывают, что <tex>t</tex> и <tex>r</tex> сильно связаны, из чего следует что <tex>t</tex> и <tex>s</tex> также сильно связаны.
+
Теперь докажем, что если <tex>s</tex> и <tex>t</tex> находятся в одном дереве поиска, то они являются сильно связанными. Пусть <tex>r</tex> - корень этого дерева. Тогда существует путь <tex>r \rightsquigarrow s</tex>, из чего следует, что в инвертированном графе есть путь <tex>s \rightsquigarrow r</tex>. Очевидно, что <tex>f[r]</tex> > <tex>f[s]</tex>, т. к. мы рассматриваем вершины в порядке убывания <tex>f[u]</tex>. Предположим, что пути <tex>s \rightsquigarrow r</tex> в исходном графе нет. Тогда в инвертированном графе нет пути <tex>r \rightsquigarrow s</tex>. Исходя из факта существования в инвертированном графе <tex>s \rightsquigarrow r</tex> и отсутствия <tex>r \rightsquigarrow s</tex>, делаем вывод, что <tex>r</tex> была посещена как потомок <tex>s</tex> или <tex>r</tex> уже была обработана поиском в глубину на момент начала поиска из <tex>s</tex>. Но тогда <tex>f[s]</tex> > <tex>f[r]</tex>, что является противоречием. Значит, наше предположение об отсутсвии пути <tex>s \rightsquigarrow r</tex> было не верно. Тогда в исходном графе существуют пути как <tex>s \rightsquigarrow r</tex>, так и <tex>r \rightsquigarrow s</tex>, т.е. <tex>r</tex> и <tex>s</tex> сильно связаны. Те же рассуждения доказывают, что <tex>t</tex> и <tex>r</tex> сильно связаны, из чего следует что <tex>t</tex> и <tex>s</tex> также сильно связаны.
  
 
==Пример реализации==
 
==Пример реализации==

Версия 00:11, 16 января 2011

Постановка задачи

Дан ориентированный граф [math]G[/math]. Требуется найти в этом графе компоненты сильной связанности.

Алгоритм

Данная задачи решается с помощью поиска в глубину в 3 этапа:

  1. Построить граф [math]H[/math] с обратными (инвертированными) рёбрами
  2. Выполнить в [math]H[/math] поиск в глубину и найти [math]f[u][/math] - время окончания обработки вершины [math]u[/math]
  3. Выполнить поиск глубину в [math]G[/math], перебирая вершины во внешнем цикле в порядке убывания [math]f[u][/math]

Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа [math]G[/math].
Так как компоненты сильной связности [math]G[/math] и [math]H[/math] графа совпадают, то первый поиск в глубину для нахождения [math]f[u][/math] можно выполнить на графе [math]G[/math], а второй - на [math]H[/math].

Доказательство

Рассмотрим пару вершин [math]s[/math] и [math]t[/math]. Если вершины [math]s[/math] и [math]t[/math] взаимно достижимы, то они обязательно будут находиться в одном дереве поиска в глубину, поскольку, когда просматривается первая из них, вторая остаётся непосещённой и достижимой из первой и будет просмотрена, прежде чем завершится рекурсивный вызов из корня.
Теперь докажем, что если [math]s[/math] и [math]t[/math] находятся в одном дереве поиска, то они являются сильно связанными. Пусть [math]r[/math] - корень этого дерева. Тогда существует путь [math]r \rightsquigarrow s[/math], из чего следует, что в инвертированном графе есть путь [math]s \rightsquigarrow r[/math]. Очевидно, что [math]f[r][/math] > [math]f[s][/math], т. к. мы рассматриваем вершины в порядке убывания [math]f[u][/math]. Предположим, что пути [math]s \rightsquigarrow r[/math] в исходном графе нет. Тогда в инвертированном графе нет пути [math]r \rightsquigarrow s[/math]. Исходя из факта существования в инвертированном графе [math]s \rightsquigarrow r[/math] и отсутствия [math]r \rightsquigarrow s[/math], делаем вывод, что [math]r[/math] была посещена как потомок [math]s[/math] или [math]r[/math] уже была обработана поиском в глубину на момент начала поиска из [math]s[/math]. Но тогда [math]f[s][/math] > [math]f[r][/math], что является противоречием. Значит, наше предположение об отсутсвии пути [math]s \rightsquigarrow r[/math] было не верно. Тогда в исходном графе существуют пути как [math]s \rightsquigarrow r[/math], так и [math]r \rightsquigarrow s[/math], т.е. [math]r[/math] и [math]s[/math] сильно связаны. Те же рассуждения доказывают, что [math]t[/math] и [math]r[/math] сильно связаны, из чего следует что [math]t[/math] и [math]s[/math] также сильно связаны.

Пример реализации

   vector<vector<int>> g, h;                                  //g хранит граф в виде списка смежностей, h - инвертированный
   vector<int> color, ord, component;                         //цвет вершины, список вершин в порядке окончания обработки, номер компоненты, к который относиться вершина
   int col;                                                   //номер текущей компоненты
   
   void dfs(int & v)                                          //первый поиск в глубину, определяющий порядок обхода
   {
       color[v] = 1;
       for (unsigned i = 0; i < g[v].size(); ++i)
       {
           if (color[g[v][i]] == 0)
               dfs(g[v][i]);
       }
       ord.push_back(v);                                      //добавляем вершину v в конец списка ord[]
   }
   
   void dfs2(int & v)                                         //второй поиск в глубину, выявляет компоненты сильной связности в графе 
   {
       component[v] = col;                                    //помечаем вершину v как принадлежащую компоненте с номером col
       for (unsigned i = 0; i < h[v].size(); ++i)
       {
           if (component[h[v][i]] == 0)                       
               dfs2(h[v][i]);
       }
   }
   
   int main()
   {
       ...                                                    //считываем исходные данные, формируем массивы g и h
       for (int i = 1; i <= n; ++i)                           //формируем массив ord[]
       {
           if (color[i] == 0)
               dfs(i);
       }
       col = 1;
       for (int i = ord.size(); i > 0; --i)                   //ищем компоненты связности, вызывая вершины в обратном порядке
       {                                                      //от сохранённого в ord[], что соответствует уменьшению времени конца обработки f[]
           if (component[ord[i - 1]] == 0)
               dfs2(ord[i - 1]), col++;
       }
   }

По окончании выполнения алгоритма в [math]component[i][/math] имеем номер компоненты, к которой принадлежит вершина [math]i[/math].

Литература

  • Р.Седжвик. "Фундаментальные алгоритмы на С++. Алгоритмы на графах" - СПб, ДиаСофтЮП, 2002