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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример реализации)
(Постановка задачи)
Строка 1: Строка 1:
 
==Постановка задачи==
 
==Постановка задачи==
Дан [[ориентированный граф]] '''''G'''''. Требуется найти в этом графе компоненты сильной связанности.
+
Дан [[ориентированный граф]] '''''G'''''. Требуется найти в этом графе [http://neerc.ifmo.ru/mediawiki/index.php/%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%B8,_%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#.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 компоненты сильной связанности].
 +
 
 
==Алгоритм==
 
==Алгоритм==
 
Данная задачи решается с помощью поиска в глубину в 3 этапа:
 
Данная задачи решается с помощью поиска в глубину в 3 этапа:

Версия 21:19, 15 января 2011

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

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

Алгоритм

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

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

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

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

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

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

   vector<vector<int>> g, g1;                                 //g хранит граф в виде списка смежностей, g1 - обратный
   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);                                     
   }
   
   void dfs2(int & v)                                         //второй поиск в глубину, выявляет компоненты сильной связности в графе 
   {
       component[v] = col;
       for (unsigned  i = 0; i < g1[v].size(); i ++ )
       {
           if (component[g1[v][i]] == 0)
               dfs2(g1[v][i]);
       }
   }
   
   int main()
   {
       ...                                                    //считываем исходные данные, формируем массивы g и g1
       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++;
       }
   }

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