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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности алгоритма)
Строка 20: Строка 20:
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
  
1) Рассмотрим корень <tex>r</tex> дерева второго обхода в глубину, в котором оказались вершины <tex>s</tex> и <tex>t</tex>. Это значит, что в графе <tex>G</tex> существует путь из <tex>r</tex> в <tex>s</tex> и в <tex>t</tex>.  
+
1) Вершины <tex>s</tex> и <tex>t</tex> оказались в одной компоненте связности, т.е. принадлежат одному и тому же дереву поиска в глубину на третьем этапе алгоритма. Значит, что они обе достижимы из корня <tex>r</tex> этого дерева.  
  
 
2) Вершина <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 случая:

Версия 10:50, 17 января 2012

Алгоритм

Компоненты сильной связанности можно найти с помощью поиска в глубину в 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]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]r[/math] в графе [math]G[/math], а значит, вершина [math]r[/math] достижима из них в графе [math]H[/math].

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