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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Постановка задачи)
(Алгоритм)
Строка 1: Строка 1:
 
==Алгоритм==
 
==Алгоритм==
Данная задачи решается с помощью поиска в глубину в 3 этапа:
+
[[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связанности]] можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в глубину]] в 3 этапа:
 
#Построить граф <tex>H</tex> с обратными (инвертированными) рёбрами  
 
#Построить граф <tex>H</tex> с обратными (инвертированными) рёбрами  
 
#Выполнить в <tex>H</tex> поиск в глубину и найти <tex>f[u]</tex> - время окончания обработки вершины <tex>u</tex>
 
#Выполнить в <tex>H</tex> поиск в глубину и найти <tex>f[u]</tex> - время окончания обработки вершины <tex>u</tex>
Строка 6: Строка 6:
 
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа <tex>G</tex>.<br>
 
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа <tex>G</tex>.<br>
 
Так как компоненты сильной связности <tex>G</tex> и <tex>H</tex> графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй - на <tex>H</tex>.
 
Так как компоненты сильной связности <tex>G</tex> и <tex>H</tex> графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй - на <tex>H</tex>.
 +
 
==Доказательство корректности алгоритма==
 
==Доказательство корректности алгоритма==
 
{{Теорема
 
{{Теорема

Версия 20:40, 23 ноября 2011

Алгоритм

Компоненты сильной связанности можно найти с помощью поиска в глубину в 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]\Leftrightarrow[/math] после выполнения алгоритма они оказываются в одной компонентe сильной связанности.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

Если вершины [math]s[/math] и [math]t[/math] были взаимно достижимы в графе [math]G[/math], то во время выполнения третьего шага алгоритма обе вершины окажутся в одном поддереве по свойству обхода в глубина. Следовательно они будут находится в одной компоненте сильной связности.

[math]\Leftarrow[/math]

1) Рассмотрим корень [math]r[/math] дерева второго обхода в глубину, в котором оказались вершины [math]s[/math] и [math]t[/math]. Это значит, что в графе [math]G[/math] существует путь из [math]r[/math] в [math]s[/math] и в [math]t[/math].

2) Вершина [math]r[/math] была рассмотрена вторым обходом в глубину раньше, чем [math]s[/math] и [math]t[/math], значит время выхода из нее при первом обходе в глубину больше, чем время выхода из вершин [math]s[/math] и [math]t[/math]. Из этого мы получаем 2 случая:

а) Обе эти вершины были достижимы из [math]r[/math] в инвертированном графе. А это означает взаимную достижимость вершин [math]s[/math] и [math]r[/math] и взаимную достижимость вершин [math]r[/math] и [math]t[/math]. А складывая пути мы получаем взаимную достижимость вершин [math]s[/math] и [math]t[/math].

б) Между [math]r[/math] и этими вершинами вообще нет пути ни в одну сторону, ни в другую при первом обходе в инверитированном графе. Но последнего быть не может, так как эти вершины были достижимы из [math]r[/math] в графе [math]G[/math], а значит, вершина [math]r[/math] достижима из них в графе [math]H[/math].

Значит, из случая а) и не существования случая б) получаем, что вершины [math]s[/math] и [math]t[/math] взаимно достижимы в обоих графах.
[math]\triangleleft[/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