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

Алгоритм

Компоненты сильной связанности можно найти с помощью поиска в глубину в 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]r[/math] дерева второго обхода в глубину, в котором оказались вершины [math]s[/math] и [math]t[/math]. Это значит, что в графе [math]G[/math] существует путь из [math]r[/math] в [math]s[/math] и в [math]t[/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, H[/math]                               //g хранит граф в виде списка смежностей, h - инвертированный
   [math]ord, component[/math]                     //список вершин в порядке окончания обработки, номер компоненты, к который относиться вершина
   
   dfs([math]v[/math])                                          //первый поиск в глубину, определяющий порядок обхода
       [math]color[v] \leftarrow 1[/math]
       for (всех [math]i[/math] смежных с [math]v[/math])
           if (вершина [math]i[/math] не посещена)
               dfs([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])                           //формируем массив ord[]
           if ( вершина [math]i[/math] не посещена)
               dfs(i);
       [math]col \leftarrow 1;[/math]
       for (по всем вершинам [math]i[/math] списка [math]ord[][/math] в обратном порядке)                                                        //от сохранённого в ord[], что соответствует уменьшению времени конца обработки f[]
           if (если вершина [math]i[/math] не находится ни в какой компоненте)
               dfs2([math]i[/math]), [math]col[/math]++;

По окончании выполнения алгоритма в [math]component[i][/math] имеем номер компоненты, к которой принадлежит вершина [math]i[/math].

Литература

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