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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

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

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: