34 2. Поиск в графе
StrongComp(x) условие в строке 9 (считая, что w = z) выполнится. По-
этому текущее значение L[x] не превосходит num[z] < num[x]. Отсюда
следует, что значение L[x ], подсчитанное процедурой, будет меньше чем
num[x]. Это противоречит выбору x.
Покажем, что в процессе выполнения процедуры StrongComp(r
1
)
условие L[r
1
] = n um[ r
1
] будет выполнено. Напомним, что множество
ˆr
1
совпадает с множеством вершин компоненты G
1
. Отсюда следует,
что V B(ˆu, u) ⊆ V B(ˆr
1
, r
1
) для любого потомка u вершины r
1
. Из тео-
ремы 2.4 вытекает, что V B(ˆr
1
, r
1
) ⊆ ˆr
1
. При выполнении процедуры
StrongComp(u) все просмотренные вершины находятся в стеке S. По-
этому значения L[u], уточняемые в строках 7 и 10 всегда будут не
меньше чем num[r
1
]. С учетом присваиваний в строке 3, имеем L[r
1
] =
= num[r
1
].
Для завершения доказательства применим индукцию по числу q ком-
понент сильной связности орграфа G.
Пусть q = 1. Тогда G = G
1
, т. е. все вершины орграфа G, о тличные
от вершины r
1
, являются ее потомками. Условие в строке 11 выполнится
только один раз при v = r
1
. Поэтому из стека S будут вытолкнуты все
вершины орграфа G.
Предположим, что q > 1. Пусть алгоритм 2.3 начинает работу с вер-
шины v
0
. В процессе работы алгоритма после завершения работы проце-
дуры DF S(r
1
) из стека S будут вытолкнуты все вершины компоненты
сильной связности G
1
. Обозначим через G
0
подграф, полученный из ор-
графа G удалением компоненты G
1
. Очевидно, к орграфу G
0
применимо
предположение индукции. Следовательно, все компоненты, отличные от
G
1
, будут найдены правильно.
2.4. Поиск в ширину
Рассмотрим еще один способ систематического обхода всех вершин
обыкновенного графа G, на зываемый поиском в ширину. Для описания
поиска в ширину введем в рассмотрение очередь Q, элементами которой
являются вершины графа G. Поиск начинается с некоторой вершины v.
Эта вершина помещается в очередь Q и с этого момента считается про-
смотренной. Затем все вершины, смежные с v включаются в очередь
и получают статус просмотренных, а вершина v из очереди удаляется.
Более общо, пусть в начале очереди находит ся вершина u. Обозначим
через u
1
, . . . , u
p
вершины, смежные с u и еще непросмотренные. Тогда
вершины u
1
, . . . , u
p
помещаются в очередь Q и с этого момента счита-