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

                                    37
соответствующего           орграфа. Сарджент и Уэстерберг предложили
простой алгоритм отыскания сильных компонент произвольного орграфа.
Алгоритм основан на процедуре поиска в глубину, поскольку в нем
прослеживается путь при сохранении насколько это возможно
последовательности вершина – ребро – вершина – ребро… Путь начинается
из произвольно взятой вершины и продолжается до тех пор, пока не будут
обнаружены либо цикл, либо вершина без выхода.
   Цикл опознается благодаря тому, что путь входит в вершину,
посещавшуюся прежде. Все вершины цикла принадлежат одной и той же
сильной компоненте. В случае обнаружения цикла применяется процедура,
называемая стягиванием вершин: все вершины цикла стягиваются в единую
составную вершину, все ребра цикла игнорируются, а ребра, соединяющие
вершины цикла с прочими вершинами графа, рассматриваются теперь как
соединяющие составную вершину с этими прочими вершинами. Составная
вершина становится последней вершиной текущего пути, и в
модифицированном графе поиск возобновляется с этого места.
Если найдена вершина, или составная вершина, не имеющая выхода, то эта
вершина или составная вершина является сильной компонентой уровня 1.
Вершина или все вершины, образующие составную, удаляются из графа
вместе со всеми инцидентными им ребрами. Поиск затем возобновляется в
оставшемся подграфе, причем отправляются от последней вершины
текущего пути либо от новой начальной вершины, если путь исчерпан. Так
продолжается до тех пор, пока не будут посещены все вершины и
исследованы все ребра исходного графа.
   В этом алгоритме каждое ребро графа исследуется только один раз.
Однако, необходимы частые перестройки графа, что составляет серьезную
дополнительную работу. Стягивание вершин при обнаружении очередного
цикла эквивалентно формированию нового факторграфа, а удаление сильной
компоненты – выделению частичного графа. Приходится вести записи,
указывающие, из каких вершин состоит каждая составная вершина и какой
составной вершине принадлежит каждая вершина исходного графа.
Неудачная реализация может повлечь O(|V|2) перепомечиваний вершин (V –
множество вершин графа G = (V, E)).

      3.2.7 Алгоритм Тарьяна
      При поиске в глубину на орграфе G = (V, E) формируется остовной лес,
состоящий из одного или нескольких деревьев. Вершины каждой сильной
компоненты C орграфа определяют поддерево некоторого дерева из леса.
Поддерево содержит все вершины C и только вершины С, его корень – это
первая вершина C, посещаемая в ходе поиска. Таким образом, задача
отыскания сильных компонент сводится к отысканию корней поддеревьев в
остовном лесу, порождаемом поиском в глубину.
   Алгоритм Тарьяна сконструирован таким образом, чтобы возвращение
через корень компоненты C в другую компоненту более высокого уровня
было невозможно до тех пор, пока все вершины C не будут посещены и