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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример реализации)
(Псевдокод)
(не показано 47 промежуточных версий 9 участников)
Строка 1: Строка 1:
==Постановка задачи==
 
Дан [[ориентированный граф]] <tex>G</tex>. Требуется найти в этом графе [[Отношение_связности,_компоненты_связности|компоненты сильной связанности]].
 
 
 
==Алгоритм==
 
==Алгоритм==
{{Определение
+
[[Файл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны.<br>Синим цветом обозначен обод DFS по инвертированным ребрам]]
|definition=
+
[[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связности]]  в графе <tex>G</tex> можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в глубину]] в 3 этапа:
Дополнением или обратным к графу <tex>G</tex> называется такой граф <tex>H</tex>, имеющий то же множество вершин, что и <tex>G</tex>, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в <tex>G</tex>}}
+
#Построить граф <tex>H</tex> с обратными (инвертированными) рёбрами
Данная задачи решается с помощью поиска в глубину в 3 этапа:
+
#Выполнить в <tex>H</tex> поиск в глубину и найти <tex>f[u]</tex> время окончания обработки вершины <tex>u</tex>
#Построить обратный граф
+
#Выполнить поиск в глубину в <tex>G</tex>, перебирая вершины  во внешнем цикле в порядке убывания <tex>f[u]</tex>
#Выполнить в обратном графе поиск в глубину и найти <tex>f[u]</tex> - время окончания обработки вершины <tex>u</tex>
 
#Выполнить поиск глубину в <tex>G</tex>, перебирая вершины  во внешнем цикле в порядке убывания <tex>f[u]</tex>
 
 
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа <tex>G</tex>.<br>
 
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа <tex>G</tex>.<br>
Так как компоненты сильной связности исходного и обратного графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй - на обратном.
+
Так как компоненты сильной связности <tex>G</tex> и <tex>H</tex> графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй на <tex>H</tex>.
===Доказательство===
+
<br clear = "all">
Рассмотрим пару вершин <tex>s</tex> и <tex>t</tex>.
+
 
Если вершины <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>r</tex> в <tex>s</tex>, т.е. <tex>r</tex> и <tex>s</tex> сильно связаны. Те же рассуждения доказывают, что <tex>t</tex> и <tex>r</tex> сильно связаны, из чего следует что <tex>t</tex> и <tex>s</tex> также сильно связаны.
+
{{Теорема
 +
|statement=
 +
Вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы <tex>\Leftrightarrow</tex> после выполнения алгоритма они принадлежат одному дереву обхода в глубину.
 +
|proof=
 +
<tex>\Rightarrow</tex>
 +
 
 +
Если вершины <tex>s</tex> и <tex>t</tex> были взаимно достижимы в графе <tex>G</tex>, то на третьем этапе будет найден путь из одной вершины в другую, это означает, что по окончанию алгоритма обе вершины лежат в одном поддереве.
 +
 
 +
<tex>\Leftarrow</tex>
 +
 
 +
# Вершины <tex>s</tex> и <tex>t</tex> лежат в одном и том же дереве поиска в глубину на третьем этапе алгоритма. Значит, что они обе достижимы из корня <tex>r</tex> этого дерева.  
 +
# Вершина <tex>r</tex> была рассмотрена вторым обходом в глубину раньше, чем <tex>s</tex> и <tex>t</tex>, значит время выхода из нее при первом обходе в глубину больше, чем время выхода из вершин <tex>s</tex> и <tex>t</tex>. Из этого мы получаем 2 случая:
 +
##Обе эти вершины были достижимы из <tex>r</tex> в инвертированном графе. А это означает взаимную  достижимость вершин <tex>s</tex> и <tex>r</tex> и взаимную достижимость вершин <tex>r</tex> и <tex>t</tex>. А складывая пути мы получаем взаимную достижимость вершин <tex>s</tex> и <tex>t</tex>.
 +
##Хотя бы одна не достижима из <tex>r</tex> в инвертированном графе, например <tex>t</tex>. Значит и <tex>r</tex> была не достижима из <tex>t</tex> в инвертированном графе, так как время выхода <tex>r</tex> - больше . Значит между этими вершинами нет пути, но последнего быть не может, потому что <tex>t</tex> была достижима из <tex>r</tex> по пункту 1).
 +
 
 +
Значит, из случая 2.1 и не существования случая 2.2 получаем, что вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы в обоих графах.
 +
}}
 +
 
 +
==Время работы алгоритма==
 +
#Для того, чтобы инвертировать все ребра в графе, представленном в виде списка потребуется <tex>O(V + E)</tex> действий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования.
 +
#Количество ребер в инвертированном равно количеству ребер в изначальном графе, поэтому поиск в глубину будет работать за <tex>O(V + E)</tex>  
 +
#Поиск в глубину в исходном графе выполняется за <tex>O(V + E)</tex>.
 +
В итоге получаем, что время работы алгоритма <tex>O(V + E)</tex>.
  
==Пример реализации==
+
==Псевдокод==
    vector<vector<int>> g, g1;                                //g хранит граф в виде списка смежностей, g1 - обратный
+
Пусть <tex>G</tex> — исходный граф, <tex>H</tex> —инвертированный граф. В массиве <tex>ord</tex> будем хранить номера вершин в порядке окончания обработки поиском в глубину в графе <tex>G</tex>. В результате получаем массив <tex>component</tex>, который каждой вершине сопоставляет номер её компоненты.
    vector<int> color, ord, component;                        //цвет вершины, список вершин в порядке окончания обработки, номер компоненты, к который относиться вершина
 
    int col;                                                  //номер текущей компоненты
 
 
      
 
      
     void dfs(int & v)                                          //первый поиск в глубину, определяющий порядок обхода
+
     '''function''' dfs1(v):                                          
    {
+
         color[v] = 1
         color[v] = 1;
+
         '''for''' (v, u) '''in''' E
         for (unsigned i = 0; i < g[v].size(); ++i)
+
             '''if''' '''not''' visited[u]
        {
+
                 dfs1(G[v][u])
             if (color[g[v][i]] == 0)
+
         Добавляем вершину v в конец списка ord
                 dfs(g[v][i]);
 
        }
 
         ord.push_back(v);                                   
 
    }
 
 
      
 
      
     void dfs2(int & v)                                         //второй поиск в глубину, выявляет компоненты сильной связности в графе
+
     '''function''' dfs2(v):                                         
    {
+
         component[v] = col
         component[v] = col;
+
         '''for''' (v, u) '''in''' E
         for (unsigned i = 0; i < g1[v].size(); ++i)
+
             '''if''' (вершина u еще не находится ни в какой компоненте)                      
        {
+
                 dfs2(H[v][u])
             if (component[g1[v][i]] == 0)
 
                 dfs2(g1[v][i]);
 
        }
 
    }
 
 
      
 
      
     int main()
+
     '''function''' main():
    {
+
         считываем исходные данные, формируем массивы G и H
         ...                                                    //считываем исходные данные, формируем массивы g и g1
+
         '''for''' u '''in''' V                            
         for (int i = 1; i <= n; ++i)                           //формируем массив ord[]
+
             '''if''' '''not''' visited[u]
        {
+
                 dfs1(u)
             if (color[i] == 0)
+
         col = 1
                 dfs(i);
+
         '''for''' (по всем вершинам u списка ord[] в обратном порядке)                                                       
        }
+
             '''if''' (вершина u не находится ни в какой компоненте)
         col = 1;
+
                 dfs2(u)
         for (int i = ord.size(); i > 0; --i)                  //ищем компоненты связности, вызывая вершины в обратном порядке
+
                col++
        {                                                      //от сохранённого в ord[], что соответствует уменьшению времени конца обработки f[]
 
             if (component[ord[i - 1]] == 0)
 
                 dfs2(ord[i - 1]), col++;
 
        }
 
    }
 
 
 
По окончании выполнения алгоритма в <tex>component[i]</tex> имеем номер компоненты, к которой принадлежит вершина <tex>i</tex>.
 
  
==Литература==
+
==Источники информации==
 
* Р.Седжвик. "Фундаментальные алгоритмы на С++. Алгоритмы на графах" - СПб, ДиаСофтЮП, 2002
 
* Р.Седжвик. "Фундаментальные алгоритмы на С++. Алгоритмы на графах" - СПб, ДиаСофтЮП, 2002
 +
* [http://e-maxx.ru/algo/strong_connected_components  MAXimal :: algo :: Поиск компонент сильной связности, построение конденсации графа]
 +
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/scc-2008/| Визуализация поиска компонент сильной связности]
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Обход в глубину]]

Версия 18:29, 4 января 2016

Алгоритм

Вершины 2, 4, 5 сильносвязаны.
Синим цветом обозначен обод DFS по инвертированным ребрам

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

[math]\Rightarrow[/math]

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

[math]\Leftarrow[/math]

  1. Вершины [math]s[/math] и [math]t[/math] лежат в одном и том же дереве поиска в глубину на третьем этапе алгоритма. Значит, что они обе достижимы из корня [math]r[/math] этого дерева.
  2. Вершина [math]r[/math] была рассмотрена вторым обходом в глубину раньше, чем [math]s[/math] и [math]t[/math], значит время выхода из нее при первом обходе в глубину больше, чем время выхода из вершин [math]s[/math] и [math]t[/math]. Из этого мы получаем 2 случая:
    1. Обе эти вершины были достижимы из [math]r[/math] в инвертированном графе. А это означает взаимную достижимость вершин [math]s[/math] и [math]r[/math] и взаимную достижимость вершин [math]r[/math] и [math]t[/math]. А складывая пути мы получаем взаимную достижимость вершин [math]s[/math] и [math]t[/math].
    2. Хотя бы одна не достижима из [math]r[/math] в инвертированном графе, например [math]t[/math]. Значит и [math]r[/math] была не достижима из [math]t[/math] в инвертированном графе, так как время выхода [math]r[/math] - больше . Значит между этими вершинами нет пути, но последнего быть не может, потому что [math]t[/math] была достижима из [math]r[/math] по пункту 1).
Значит, из случая 2.1 и не существования случая 2.2 получаем, что вершины [math]s[/math] и [math]t[/math] взаимно достижимы в обоих графах.
[math]\triangleleft[/math]

Время работы алгоритма

  1. Для того, чтобы инвертировать все ребра в графе, представленном в виде списка потребуется [math]O(V + E)[/math] действий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования.
  2. Количество ребер в инвертированном равно количеству ребер в изначальном графе, поэтому поиск в глубину будет работать за [math]O(V + E)[/math]
  3. Поиск в глубину в исходном графе выполняется за [math]O(V + E)[/math].

В итоге получаем, что время работы алгоритма [math]O(V + E)[/math].

Псевдокод

Пусть [math]G[/math] — исходный граф, [math]H[/math] —инвертированный граф. В массиве [math]ord[/math] будем хранить номера вершин в порядке окончания обработки поиском в глубину в графе [math]G[/math]. В результате получаем массив [math]component[/math], который каждой вершине сопоставляет номер её компоненты.

   function dfs1(v):                                          
       color[v] = 1
       for (v, u) in E
           if not visited[u]
               dfs1(G[v][u])
       Добавляем вершину v в конец списка ord
   
   function dfs2(v):                                          
       component[v] = col
       for (v, u) in E
           if (вершина u еще не находится ни в какой компоненте)                       
               dfs2(H[v][u])
   
   function main():
       считываем исходные данные, формируем массивы G и H
       for u in V                           
           if not visited[u]
               dfs1(u)
       col = 1
       for (по всем вершинам u списка ord[] в обратном порядке)                                                        
           if (вершина u не находится ни в какой компоненте)
               dfs2(u)
               col++

Источники информации