ный графы заданы с помощью списков смежных вершин). Легко понять, что G и GT имеют одни и те же сильно связные компоненты (поскольку v достижимо из и в GT, если и только если и достижимо из v в GT). На рисунке 23.9 (Ь) показан трезультат транспонирования графа рис. 23.9 (а).

Следующий алгоритм находит сильно связные компоненты ориентированного графа G = (V,E), используя два поиска в глубину - для G и для GT; время работы есть 0(V + Е).

Strongly-Connected-Components($G$)

1с помощью DFS($G$) найти время окончания обработки $f [и]$ для каждой вершины $и$

2построить $G~T$

3вызвать DFS($G~T$), при этом в его внешнем цикле перебирать вершины в порядке убывания величны $f[и]$ (вычисленной в строке 1)

4сильно связными компонентами будут деревья поиска, построенные на шаге 3.

С первого взгляда этот алгоритм кажется несколько загадочным. Его анализ мы начнём с двух полезных наблюдений, относящихся к произвольному ориентированному графу.

Лемма 23.12

Если две вершины принадлежат одной сильно связной компоненте, никакой путь между ними не выходит за пределы этой компоненты.

Доказательство.

Пусть вершина w лежит на пути из и и v, и вершины и и v принадлежат одной сильно связной компоненте. Тогда и w, w v и v и, откуда всё и следует.

Теорема 23.13

В процессе поиска в глубину вершины одной сильно связной компоненты попадают в одно и то же дерево. Доказательство.

Для произвольной сильно связной компоненты рассмотрим её вершину, обнаруженную первой (обозначим её г). В этот момент все остальные вершины компоненты ещё белые и потому доступны из г по белым путям (ведущие в них пути не выходят за пределы компоненты по лемме 23.12). Поэтому по теореме о белом пути они будут закрашены при вызове DFS-VlslT(r) и войдут в то же дерево поиска.

Возвращаясь к анализу алгоритма Strongly-Connected-Components, договоримся, что d[u] и f[u] будут обозначать время обнаружения и время окончания обработки вершины v, найденные в строке 1 алгоритма, а запись и v будет означать существование пути в С (а не в GT).

Для каждой вершины и графа определим её предшественника (forefather) <~р{и) как ту из вершин w, достижимых из и, для которой

обработка была завершена позднее всех:

<р(и) = такая вершина w, что и w и f[w] максимально

При этом вполне может оказаться, что <~р(и) = и. Так как любая вершина и достижима сама из себя,

Докажем теперь, что <р(<р(и)) = (р(и). В самом деле, для любых двух вершин и, v £ V

потому что {w : v w} С {w : и w} и предшественник любой вершины имеет максимальное время завершения обработки среди всех достижимых из неё вершин. Поскольку вершина <~р(и) достижима из и, из формулы (23.3) получаем, что /[ср(ср(и))] f[(p(u)]. Кроме того, из неравенства (23.2) имеем f[(f(u)] /[ср(ср(и))]. Следовательно f[(p((p(u))] = f[<-p(u)~\ и <р(<р(и)) = (и), так как две вершины с одним временем завершения обработки.

Как мы увидим, в каждой сильно связной компоненте есть вершина, являющаяся предшественником всех вершин этой компоненты. При поиске в глубину в G эта вершина обнаруживается первой и оказывается обработанной последней (среди вершин этой компоненты). При поиске в GT она становится корнем дерева поиска в глубину. Давайте докажем эти свойства.

Фиксируем некоторую сильно связную компоненту S. Рассмотрим вершину v этой компоненты, которая обнаруживается (при поиске в глубину) первой, то есть имеет минимальное значение d[v] среди всех v £ S. Изучим ситуацию, которая имеет место непосредственно перед вызовом DFS-Visit(C).

1.В этот момент все вершины из S белые. (Если это не так, вершина v не является первой обнаруженной вершиной из S.)

2.Все вершины компоненты S достижимы из v по белым путям. (В самом деле, по лемме 23.12 пути не выходят за пределы S.)

3.Ни одна серая вершина не достижима из v. (В самом деле, в момент вызова DFS-Visit(u) серые вершины образуют путь из корня дерева поиска в v, поэтому v достижима из любой серой вершины. Если бы некоторая серая вершина была достижима из v, то она лежала бы в одной компоненте с v, а все такие вершины белые.)

4.Любая белая вершина w, достижимая из v, достижима по белому пути. (В самом деле, на пути из v в w не может быть серых вершин, поэтому все вершины этого пути или белые, иили чёрные. С другой стороны, при поиске в глубину никогда не возникает ребра из чёрной вершины в белую, поэтому на этом пути не может быть чёрных вершин.)

f[u] f[V{u)\

и v => f[(f(v)] f[<f(u)]

(23.3)

5.Все вершины компоненты S будут закрашены при вызове DFS-Visit(u) и будут потомками v в дереве поиска. (Следует из теоремы о белом пути.)

6.Все вершины, достижимые из v, имеют меньшее время завершения обработки, чем сама v. (В самом деле, для чёрных вершин это очевидно, так как они уже были обработаны к моменту начала обработки v. Для белых это тоже верно, поскольку они будут обработаны в ходе вызова DFS-Visit(u) до окончания обработки

7.Вершина v является собственным предшественником: <-p{v) = v. (Другая формулировка предыдущего утверждения.)

8.Вершина v является предшественником любой вершины и компоненты S. (В самом деле, из и достижимы те же вершины, что из v, и потому вершина с максимальным временем завершения будет той же самой).

Мы видим, что в каждой сильно связной компоненте есть вершина, которая обнаруживается первой, завершает обрабатываться последней и является предшествеником всех вершин этой компоненты.

Таким образом, мы доказали следующие утверждения: Теорема 23.14

В ориентированном графе G = (V, Е) предшественник <~р{и) любой вершины и £ V оказывается её предком в дереве поиска в глубину.

Следствие 23.15

При любом поиске в глубину на ориентированном графе G = (V, Е) вершины и и <~р{и) лежат в одной сильно связной компоненте для любой и G V.

Теорема 23.16

В ориентированном графе G = (V, Е) две вершины лежат в одной сильно связной компоненте тогда и только тогда, когда они имеют общего предшественника при поиске в глубину.

Итак, задача о нахождении сильно связных компонент свелась к задече отыскания предшественников всех вершин графа. Именно для этого используется поиск в глубину в строке 3 алгоритма Strongly-Connected-Components.

Чтобы понять, как это делается, рассмотрим сначала вершину г с максимальным значением f[v] среди всех вершин графа G. (Говоря о значениях f[v], мы имеем в виду значения, вычисленные в строке 1 алгоритма.) Это вершина будет предшественником любой вершины, из которой она достижима (ни одна вершина графа не имеет большего значения /[и]). Таким образом, одну сильно связную компоненту мы нашли - это вершины, из которых достижима г. Другими словами, это вершины, достижимые из v в транспонированном графе.

Отбросив все вершины найденной компоненты, возьмём среди