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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
Строка 1: Строка 1:
 
==Алгоритм==
 
==Алгоритм==
 
[[Файл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны.<br>Синим цветом обозначен обод DFS по инвертированным ребрам]]
 
[[Файл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны.<br>Синим цветом обозначен обод DFS по инвертированным ребрам]]
[[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связанности]]  в графе <tex>G</tex> можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в глубину]] в 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>

Версия 10:51, 16 ноября 2013

Алгоритм

Вершины 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 случая:

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

Значит, из случая а) и не существования случая б) получаем, что вершины [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], который каждой вершине сопоставляет номер её компоненты.

   dfs1([math]v[/math])                                          
       [math]color[v] \leftarrow 1[/math]
       for (всех [math]i[/math] смежных с [math]v[/math])
           if (вершина [math]i[/math] не посещена)
               dfs1([math]G[v][i][/math])
       Добавляем вершину [math]v[/math] в конец списка [math]ord[/math]
   
   dfs2([math]v[/math])                                          
       [math]component[v] \leftarrow col[/math]
       for (всех [math]i[/math] смежных с [math]v[/math])
           if (если вершина [math]i[/math] еще не находится ни в какой компоненте)                       
               dfs2([math]H[v][i][/math])
   
   main()
       считываем исходные данные, формируем массивы [math]G[/math] и [math]H[/math]
       for (по всем вершинам [math]i[/math] графа [math]G[/math])                           
           if (вершина [math]i[/math] не посещена)
               dfs1(i)
       [math]col \leftarrow 1[/math]
       for (по всем вершинам [math]i[/math] списка [math]ord[][/math] в обратном порядке)                                                        
           if (если вершина [math]i[/math] не находится ни в какой компоненте)
               dfs2([math]i[/math])
               [math]col[/math]++

Литература

  • Р.Седжвик. "Фундаментальные алгоритмы на С++. Алгоритмы на графах" - СПб, ДиаСофтЮП, 2002