Методы работы с разреженными матрицами произвольного вида. Глушакова Т.Н - 39 стр.

                                     39
переопределяется. Алгоритм будет работать            правильно     и     при
ослабевании требования о том, чтобы v и ω принадлежали одной компоненте.
Действительно, если (v → ω) – древесное ребро, а v и ω относятся к разным
компонентам, то ω – корень своей компоненты. Поскольку имеет место
возвращение, то Связка(ω) = Номер(ω) > Номер(v). Так как Связка(v) ≤
Номер(v), то значение признака Связка(v) в данном случае шагом 3 не будет
изменено.
    Покажем, что признак Связка вычисляется верно. Пусть v – некоторая
вершина, относящаяся к сильной компоненте C, и пусть Tv – поддерево с
корнем v, содержащее потомство v в C. Если v не является корнем C, то Tv
должно иметь выход в эту компоненту, т.е. должно существовать ребро (ω →
x), где ω 0 Tv, x 0 C, причем это ребро недревесное. Следовательно, x должна
быть нумерована раньше, чем ω. Более того, x должна быть нумерована
раньше, чем v, чтобы ребро (ω → x) могло быть выходом из Tv, поэтому
Номер(x) < Номер(v). Ребро (ω → x) было найдено в ходе поиска, так что
Связка(ω) ≤ Номер(x). Позже, при возвращении, это значение было спущено
к v, откуда Связка(v) ≤ Номер(x) < Номер(v). Это как раз тот тест, который
определяет, что v не является корнем C. Заметим, что полученный результат
будет справедлив независимо от того, полагаем мы Связка(ω) = Номер(x) или
Связка(ω) = Связка(x) в момент обнаружения ребра (ω→x). Если v – корень
сильной компоненты, то Tv не имеет выхода, и Связка(v)=Номер(v).
    Алгоритм Тарьяна по существу совпадает с алгоритмом Сарджента –
Уэстерберга. Главное отличие заключается в том, что вместо понятия
«стягивание вершин», использовавшегося Сарджентом и Уэстербергом, в
алгоритме Тарьяна вводится признак Связка, позволяющий хранить
составные вершины в стеке. Действительно, если Связка(v) = ω, то все
вершины, находящиеся в стеке между (также помещенными туда)
вершинами ω и v, образуют составную вершину.
    Приведем развернутую формулировку алгоритма Тарьяна. Полный
алгоритм представляет собой комбинацию поиска в глубину и описанной
выше процедуры вычисления признака Связка. Используются два стека, мы
будем придерживаться терминологии Тарьяна и называть их соответственно
«стеком» и «маршрутом». Маршрут содержит список вершин, образующих
путь от начальной вершины к текущей. Каждая новая вершина, найденная
при поиске, опускается в маршрут. Каждый раз, когда выполняется
возвращение, соответствующая вершина поднимается с верха маршрута.
    Стек     содержит      список    вершин,     принадлежащих      частично
сформированным сильным компонентам. Каждая новая вершина, найденная
при поиске, опускается в стек. Вершины не удаляются из стека
индивидуально. Когда сильная компонента в верхней части стека
сформирована полностью, она удаляется вся.
    Алгоритм использует также массивы Номер и Связка, булевский массив
для проверки за фиксированное время, находится ли вершина в стеке, и
представления множества Vv посещенных вершин и множества Ee
исследованных ребер. Точная формулировка алгоритма такова: