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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности алгоритма)
(Псевдокод)
 
(не показано 19 промежуточных версий 7 участников)
Строка 1: Строка 1:
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обход в глубину]]
 
 
==Алгоритм==
 
==Алгоритм==
[[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связанности]] можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в глубину]] в 3 этапа:
+
[[Файл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны.<br>Синим цветом обозначен обод DFS по инвертированным ребрам]]
 +
[[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связности]] в графе <tex>G</tex> можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в глубину]] в 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>
Строка 8: Строка 7:
 
Полученные на 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>.
 +
<br clear = "all">
  
 
==Доказательство корректности алгоритма==
 
==Доказательство корректности алгоритма==
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы <tex>\Leftrightarrow</tex> после выполнения алгоритма они оказываются в одной [[Отношение_связности,_компоненты_связности#Сильная связность|компонентe сильной связанности]].
+
Вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы <tex>\Leftrightarrow</tex> после выполнения алгоритма они принадлежат одному дереву обхода в глубину.
 
|proof=
 
|proof=
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
  
Если вершины <tex>s</tex> и <tex>t</tex> были взаимно достижимы в графе <tex>G</tex>, то во время выполнения третьего шага алгоритма обе вершины окажутся в одном поддереве по свойству обхода в глубину. Следовательно они будут находится в одной компоненте сильной связности.
+
Если вершины <tex>s</tex> и <tex>t</tex> были взаимно достижимы в графе <tex>G</tex>, то на третьем этапе будет найден путь из одной вершины в другую, это означает, что по окончанию алгоритма обе вершины лежат в одном поддереве.
  
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
  
1) Вершины <tex>s</tex> и <tex>t</tex> оказались в одной компоненте связности, т.е. принадлежат одному и тому же дереву поиска в глубину на третьем этапе алгоритма. Значит, что они обе достижимы из корня <tex>r</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 случая:
2) Вершина <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).
  
а) Обе эти вершины были достижимы из <tex>r</tex> в инвертированном графе. А это означает взаимную  достижимость вершин <tex>s</tex> и <tex>r</tex> и взаимную достижимость вершин <tex>r</tex> и <tex>t</tex>. А складывая пути мы получаем взаимную достижимость вершин <tex>s</tex> и <tex>t</tex>.
+
Значит, из случая 2.1 и не существования случая 2.2 получаем, что вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы в обоих графах.
 
 
б) Между <tex>r</tex> и этими вершинами вообще нет пути ни в одну сторону, ни в другую при первом обходе в инверитированном графе. Но последнего быть не может, так как эти вершины были достижимы из <tex>r</tex> по пункту 1).
 
 
 
Значит, из случая а) и не существования случая б) получаем, что вершины <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>  
 
#Поиск в глубину в исходном графе выполняется за <tex>O(V + E)</tex>.
 
#Поиск в глубину в исходном графе выполняется за <tex>O(V + E)</tex>.
Строка 40: Строка 37:
 
Пусть <tex>G</tex> — исходный граф, <tex>H</tex> —инвертированный граф. В массиве <tex>ord</tex> будем хранить номера вершин в порядке окончания обработки поиском в глубину в графе <tex>G</tex>. В результате получаем массив <tex>component</tex>, который каждой вершине сопоставляет номер её компоненты.
 
Пусть <tex>G</tex> — исходный граф, <tex>H</tex> —инвертированный граф. В массиве <tex>ord</tex> будем хранить номера вершин в порядке окончания обработки поиском в глубину в графе <tex>G</tex>. В результате получаем массив <tex>component</tex>, который каждой вершине сопоставляет номер её компоненты.
 
      
 
      
     '''dfs1'''(<tex>v</tex>)                                           
+
     '''function''' dfs1(v):                                          
         <tex>color[v] \leftarrow 1</tex>
+
         color[v] = 1
         '''for''' (всех <tex>i</tex> смежных с <tex>v</tex>)
+
         '''for''' (v, u) '''in''' E
             '''if''' (вершина <tex>i</tex> не посещена)
+
             '''if''' '''not''' visited[u]
                '''dfs1'''(<tex>G[v][i]</tex>)
+
                dfs1(G[v][u])
         Добавляем вершину <tex>v</tex> в конец списка <tex>ord</tex>
+
         Добавляем вершину v в конец списка ord
 
      
 
      
     '''dfs2'''(<tex>v</tex>)                                           
+
     '''function''' dfs2(v):                                          
         <tex>component[v] \leftarrow col</tex>
+
         component[v] = col
         '''for''' (всех <tex>i</tex> смежных с <tex>v</tex>)
+
         '''for''' (v, u) '''in''' E
             '''if''' (если вершина <tex>i</tex> еще не находится ни в какой компоненте)                       
+
             '''if''' (вершина u еще не находится ни в какой компоненте)                       
                 '''dfs2'''(<tex>H[v][i]</tex>)
+
                 dfs2(H[v][u])
 
      
 
      
     '''main'''()
+
     '''function''' main():
         считываем исходные данные, формируем массивы <tex>G</tex> и <tex>H</tex>
+
         считываем исходные данные, формируем массивы G и H
         '''for''' (по всем вершинам <tex>i</tex> графа <tex>G</tex>)                            
+
         '''for''' u '''in''' V                            
             '''if''' (вершина <tex>i</tex> не посещена)
+
             '''if''' '''not''' visited[u]
                '''dfs1'''(i)
+
                dfs1(u)
         <tex>col \leftarrow 1</tex>
+
         col = 1
         '''for''' (по всем вершинам <tex>i</tex> списка <tex>ord[]</tex> в обратном порядке)                                                         
+
         '''for''' (по всем вершинам u списка ord[] в обратном порядке)                                                         
             '''if''' (если вершина <tex>i</tex> не находится ни в какой компоненте)
+
             '''if''' (вершина u не находится ни в какой компоненте)
                 '''dfs2'''(<tex>i</tex>)
+
                 dfs2(u)
                 <tex>col</tex>++
+
                 col++
  
==Литература==
+
==Источники информации==
 
* Р.Седжвик. "Фундаментальные алгоритмы на С++. Алгоритмы на графах" - СПб, ДиаСофтЮП, 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++

Источники информации[править]