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

                                                 30

      3.2.2 Поиск в ширину на       орграфе и структуры уровней
      ориентированной смежности
     Рассмотрим класс разбиений слабо связного орграфа G = (V, E),
которые могут быть построены посредством поиска в ширину.
Подструктура уровней ориентированной смежности L0, L1, …, Lm
получается, если L0δV – заданное подмножество вершин G, а каждый из
остальных уровней является смежным множеством для объединения
предыдущих уровней:
                                 �   i −1    �
                      Li = Adj ��    Υ L j ��    , i = 1, 2, …, m.
                                 �   j =0    �
   Число m называется длиной подструктуры уровней. Ширина определяется
как максимальное число вершин в произвольном уровне. L0 – корень
подструктуры. Если L0 состоит из единственной вершины u, т.е. L0 = {u}, то
будем говорить, что вершина u – корень подструктуры. Множество вершин
подструктуры
                                                   m
                                        Vs =Υ Li
                                                  i =0
содержит все вершины L0 и те вершины, которые из них достижимы. В Vs,
возможно, входят не все вершины G. В этом случае оставшееся
подмножество V–Vs может быть разбито аналогичным образом, и так далее,
пока не будет получена структура уровней ориентированной смежности,
охватывающая все вершины G. Нумерация уровней в каждой подструктуре
своя.
   Вершины при поиске группируются по уровням, а ориентированные
ребра квалифицируются как древесные либо как поперечные. Предположим,
что поиск начинается с некоторой (произвольно выбранной) начальной
вершины s. Тогда уровень L0 состоит из единственной вершины s, и будет
получена подструктура уровней с корнем в s. Пусть на некотором шаге
поиска уже опознаны все вершины уровня Li. Все вершины из Li и
предыдущих уровней помечены как посещенные. Далее для некоторого v0Li
мы исследуем ребра, ведущие из v к другим вершинам. Если найдено ребро
(v → ω), причем вершина ω еще не посещалась, то это ребро древесное, а ω
принадлежит уровню Li+1. Если найдено ребро (v → x) и x – посещенная
вершина, то это ребро поперечное. Поскольку посещенные вершины
имеются лишь в уровнях Lj, j ≤ i +1, поперечное ребро, исходящее из
вершины уровня Li, может вести только в вершину уровня Lj, j ≤ i +1. В
более общем случае, когда уже построены некоторые другие подструктуры,
поперечное ребро может вести также и в любую вершину этих подструктур.
Древесное ребро может соединять лишь вершину уровня Li и вершину
уровня Li+1, если j > i + 1, то вершина уровня Li и вершина уровня Lj не
могут быть соединены. Граф Gs =(Vs, Es), где Es – множество древесных
ребер, представляет собой дерево с корнем s, остовное для подструктуры.
Если по завершении очередного дерева продолжать поиск, начиная с новой,