8.6.3. Выделение компонент сильной связности

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

Алгоритм 8.2. Выделение компонент сильной связности Вход: орграф G(V, Е), заданный списками смежности Г(г;).

Выход: список С компонент сильной связности, каждый элемент которого есть список вершин, входящих в компоненту сильной связности. С: = 0 for v e V do

M[v]: ={v} { M[v] список вершин, входящих в ту же КСС, что и v }

e[v]: = 0 { все вершины не рассмотрены } end for while V ф 0 do

select v g V { взять v из V }

Т <— v { положить v в стек }

е[г>]: = 1 { отметить v }

КСС { вызов процедуры КСС } end while

Основная работа выполняется рекурсивной процедурой без параметров КСС, которая использует стек Т для хранения просматриваемых вершин. Процедура КСС выделяет все КСС, достижимые из вершины, выбранной в основном алго­ритме.

if Т = 0 then

return{ негде выделять }

end if

v <— Т; v —» Т { стоим в вершине г>} if T[v] П V = 0 then

C: = C\JM[v] {этоКСС } V : = V \ {v} { удалить вершину } v «— Т { снять г) со стека } КСС { возврат из тупика } else

for и 6 Г[г>] do if e[u] = 0 then u —> Г { положить и в стек } е[и]: = 1 { отметить и } else repeat

w <— Т { ш — склеиваемая вершина } \/ _: = V \ {w} { удалить ее } Г [и]: = Г [и] U Г [ад] { запомнить смежность } М[и] : = М[и} U М[го]{ склеивание вершин } until и = w

w —>• Т{ чтобы не убрать ту вершину, } V : = V U {w}{ к которой слили } end if

КСС { поиск в глубину }

end for

end if

Кратчайшие пути

Задача нахождения кратчайшего пути в графе имеет столько практических при­менений и интерпретаций, что читатель, без сомнения, может сам легко привести множество примеров. Здесь рассматриваются два классических алгоритма, кото­рые обязан знать каждый программист.