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

                                     31
не посещавшейся до сих пор вершины, и так до тех пор, пока не
будут исчерпаны все вершины G, то, в конечном счете, будут получены
джунгли и остовной лес.
   Для подструктуры уровней с корнем в s имеет место следующее свойство:
если v0Li, то расстояние в G от s до v (т.е. длина кратчайшего пути из s в v)
равно i. Кроме того, в остовном дереве существует ровно один кратчайший
путь длины i, он составлен из древесных ребер.

       3.2.3 Отыскание максимального множества путей с
       различными вершинами в ациклическом орграфе
      Рассмотрим задачу, которая связана с приведением разреженной
матрицы общего вида к блочной нижней треугольной форме посредством
несимметричных перестановок. Заданы ациклический орграф G = (V, E) и
две его вершины s, t0V, найти максимальное множество путей из s в t таких,
что ни одна вершина, кроме s и t, не принадлежит более чем одному пути.
Будем говорить, что множество максимально в смысле некоторого свойства,
если для его элементов это свойство выполнено, и оно (множество) не
включается строгим образом ни в какое другое множество элементов,
имеющих данное свойство. С другой стороны, наибольшим будем называть
множество с наибольшим числом элементов.
   Для решения обсуждаемой задачи используется поиск в глубину. Если
поиск начинается с вершины s и существует хотя бы один путь из s в t, то t
принадлежит дереву с корнем в s. Поэтому достаточно исследовать только
это дерево. Алгоритм пользуется стеком, где хранится последовательность
вершин от s до текущей вершины. Каждое ребро исследуется только один
раз, и либо оно становится частью конструируемого пути, либо не
существует пути из s в t, содержащего это ребро. Рассматриваются только
ребра, ведущие к непосещавшимся вершинам, потому что мы ищем пути, у
которых кроме концов s и t нет общих вершин. Так как возможно, что
алгоритму придется исследовать несколько ребер, ведущих к t, принимается
соглашение о том, что t не должна становиться посещенной вершиной. Если
ход поиска приведет к вершине t, она опускается в стек, который в этом
случае содержит полный путь из s в t. Все вершины поднимаются из стека и
печатаются, затем в стек снова опускается s, и начинается поиск нового пути.
Алгоритм заканчивает работу, когда s поднимается из стека после того, как
были исследованы все выходы из s. Пусть Vv – множество посещенных
вершин, Ee – множество исследованных ребер. Пусть граф представлен
своей структурой смежности. Тогда алгоритм можно описать следующим
образом:
   Шаг 0 (Инициализация). Положить Vv ← ι, Ee ← ι.
   Шаг 1 (Начало пути). Опустить s в стек.
   Шаг 2 (Посещение вершины). Положить v ← вершина наверху стека.
   Шаг 3 (Исследование ребра). Найти в списке смежности вершины v ребро
(v→ω)⌠ Ee, где ω⌠ Vv. Тогда: