Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 19, Орграфы и ориентированные ациклические графы. лял бы s с более высоким номером в результате обратного обхода
|
|
лял бы s с более высоким номером в результате обратного обхода. В силу сказанного выше, существуют ориентированные пути из s в r и из r в s в как в орграфе, так и в его обращении, отсюда следует, что s и r сильно связаны. Те же рассуждения доказывают, что t и r сильно связаны, и в силу этого обстоятельства s и t также сильно связаны. ■
Реализация алгоритма Косарайю для орграфа, представленного в виде матрицы смежности, даже проще, чем программа 19.10, поскольку в этом случае не нужно вычислять обратный граф в явном виде; решение этой задачи мы оставляем читателю на самостоятельную проработку (см. упражнение 19.125).
Программа 19.11. Сильные компоненты (алгоритм Тарьяна)_____________________
Класс DFS представляет собой еще одну реализацию того же интерфейса, что применялся в программе 19.10. Он использует стек S для хранения каждой вершины до тех пор, пока не выяснится, что все вершины в верхней части стека до определенного уровня принадлежат одной и той же сильной компоненте. Вектор low, индексированный именами вершин, отслеживает вершину с наименьшим номером в прямом порядке обхода, достижимую из каждого узла через некоторую последовательность прямых связей, за которыми следует одна восходящая связь (см. рассуждения по тексту раздела).
#include " STACK.ее" template < class 6raph> class SC { const Graph & G; STACK< int> S; int cnt, scnt; vector< int> pre, low, id; void scR(int w) { int t;
int min = low[w] = pre[w] = cnt++; S.push(w);
typename Graph:: adjIterator A(G, w); for (t = A.beg();! A.end(); t = A.nxt())
{
if (pre[t] == -1) scR(t); if (low[t] < min) min = low[t]; }
if (min < low[w]) { low[w] = min; return; } do
{ id[t = S.pop()] = scnt; low[t] = G.V(); } while (t! = w); scnt++; } public:
SC(const Graph & G): G(G), cnt(O), scnt(O), pre(G.V(), -1), low(G.V()), id(G.V()) { for (int v = 0; v < G.V(); v++)
if (pre[v] == -1) scR(v); } int count() const { return scnt; } bool stronglyreachable (int v, int w) const
{ return id[v] == id[w]; } >;
Программа 19.10 представляет собой оптимальное решение задачи сильной связности, аналогичную решениям задачи связности, рассмотренным в главе 18. В разделе 19.9 мы проведем исследование расширения этого решения на вычисление задачи транзитивного замыкания и решим задачу достижимости (абстрактно-транзитивного замыкания) в орграфах.
Часть 5. Алгоритмы на графах
Сначала, однако, мы рассмотрим алгоритм Тарьяна и алгоритм Габова - оригинальные методы, требующие внесения всего лишь небольших исправлений в нашу базовую процедуру поиска в глубину. Они предпочтительнее, чем алгоритм Косарайю, поскольку используют только один проход по графу и в силу того, что не требуют обращения для разреженных графов.
Алгоритм Тарьяна - это аналог программы, которую мы изучали в главе 17 с целью обнаружения мостов в неориентированных графах (см. программу 18.7). Этот метод основан на двух наблюдениях, которые мы сделали в других контекстах. Во-первых, мы рассматриваем вершины в обратном топологическом порядке, поэтому, когда мы достигнем конца рекурсивной функции для вершины, которую знаем, мы не встретим ни одной вершины из той же сильной компоненты (в силу того, что все вершины, достижимые из этой вершины, уже подверглись обработке). Во-вторых, обратные связи в дереве обеспечивают второй путь из одной вершины в другую и связывают между собой сильные компоненты.
Рекурсивная функция DFS использует те же вычисления, что и программа 18.7, с целью определения достижимой вершины с максимальным номером (через обратную связь) из любого потомка в каждой вершине. Она использует также вектор, индексированный именами вершин, для хранения сильных компонент и стек для отслеживания текущего пути поиска. Она заталкивает имена вершин в стек на входе в рекурсивную функцию, затем выталкивает их из стека и назначает номера компонентам после посещения завершающего элемента каждой сильной компоненты. Этот алгоритм построен на нашей способности фиксировать этот момент при помощи простой проверки (в основе которой лежит отслеживание предка с максимальным номером, достижимого через одну восходящую связь из всех потомков каждого узла) в конце рекурсивной процедуры, которая сообщает, что все вершины, встреченные с момента вхождения (за исключением тех, которые уже были назначены компоненте) принадлежат той же сильной компоненте.
Реализация в виде программы 19.11 представляет собой полное описание рассматриваемого алгоритма в сжатой форме, содержащее все необходимые подробности, которых не хватает в данном выше общем описании. Рисунок 19.29 служит иллюстрацией работы рассматриваемого алгоритма на демонстрационном примере орграфа, показанного на рис. 19.1.
Свойство 19.15. Алгоритм Тарьяна находит сильные компоненты орграфа за линейное время.
Набросок доказательства: Если у вершины s нет потомков или восходящих связей в дереве DFS, либо если у нее есть потомок в дереве DFS с восходящей связью, которая указывает на s, и нет потомков с восходящими связями, которые направлены в верхнюю часть дерева, тогда она и все ее потомки (за исключением тех вершин, которые удовлетворяют тому же свойству, и их потомки) составляют сильную компоненту. Чтобы установить этот факт, заметим, что каждый потомок t вершины s, который не удовлетворяет сформулированному свойству, имеет потомка, обладающего восходящей связью, указывающей на вершину, которая в дереве выше t. Существует путь из s в t вниз по дереву, а мы можем найти путь из t в s следующим образом: спустимся вниз по дереву из t в вершину с восходящей связью, которая ведет в вершину, расположенную выше t, затем продолжаем тот же процесс из этой вершины, пока не достигнем s.
Как обычно, этот метод линеен по времени, поскольку в данном случае к стандартному DFS добавляется несколько операций, выполняющихся за постоянное время. ■
Глава 19. Орграфы и ориентированные ациклические графы
РИСУНОК 19.29. ВЫЧИСЛЕНИЕ СИЛЬНЫХ КОМПОНЕНТ (АЛГОРИТМЫ ТАРЬЯНА И ГАБОВА)
В основе алгоритма Тарьяна лежит рекурсивный поиск в глубину, в который добавлена операция проталкивания вершин в стек. Он вычисляет индекс компоненты для каждой вершины в векторе id, индексированном именами вершин, используя векторы preи low (в центре). Дерево DFS (дерево поиска в глубину) для рассматриваемого примера графа показано в верхней части рисунка. Трассировка ребер показана внизу слева. В центре нижней части находится содержимое главного стека: мы заталкиваем в него вершины, достижимые через древесные ребра. Воспользовавшись поиском в глубину с тем, чтобы рассматривать вершины в обратном топологическом порядке, мы вычисляем для каждой вершины v максимальную точку, достижимую через обратную связь из предшественника (low[v]). Когда для вершины v выполняется pre[v]— low[v] (в данном случае это вершины 11, 1, 0 и 7), мы выталкиваем ее из стека, а также все вершины выше ее и всем им присваиваем номер следующей компоненты.
В алгоритме Габова мы снова заталкиваем вершины в главный стек точно так же, как и в алгоритме Тарьяна, но в то же время мы поддерживаем и второй стек (внизу справа), в который заталкиваются вершины, лежащие на пути поиска (о последних известно, что они находятся в различных сильных компонентах), и выталкиваем все вершины после достижения каждого обратного ребра. Если мы завершаем обработку вершины v, когда v находится на верхушке второго стека (заштриховано), мы знаем, что все вершины, расположенные над v в главном стеке, находятся в одной и той же сильной компоненте.
Часть 5. Алгоритмы на графах
В 1999 году Габов обнаружил в программе 19.12 версию алгоритма Тарьяна. Этот алгоритм поддерживает такой же стек вершин и тем же способом, что и алгоритм Тарьяна, но в то же время он использует второй стек (вместо вектора, индексированного именами вершин, в котором хранились номера вершин при обходе в прямом порядке) с тем, чтобы знать, когда выталкивать из главного стека все вершины каждой сильной компоненты. Во втором стеке содержатся вершины, входящие в траекторию поиска. Когда обратное ребро показывает, что некоторая последовательность таких вершин целиком принадлежит одной и той же сильной компоненте, мы освобождаем этот стек, оставляя в нем только вершину назначения обратного ребра, которая ближе к корню дерева, чем любая другая вершина. По завершении обработки всех ребер каждой вершины (при этом выполняются рекурсивные вызовы всех ребер дерева, освобождается стек пути для обратных ребер и игнорируются прямые ребра), мы проверяем, находится ли текущая вершина в верхушке стека пути. Если она там, то она и все вершины, расположенные сверху нее в главном стеке, составляют сильную компоненту; мы выталкиваем их из стека и присваиваем им номер следующей сильной компоненты, как это делалось в алгоритме Тарьяна.
Пример на рис. 19.29 показывает содержимое этого второго стека. Следовательно, данная диаграмма может служить иллюстрацией работы алгоритма Габова.
Свойство 19.16. Алгоритм Габова находит сильные компоненты орграфа за линейное время.
Формализацию только что изложенных аргументов и доказательство отношений, связывающих содержимое стеков, на котором оно основано, мы оставляем на самостоятельную проработку (см. упражнение 19.132) для читателей, имеющих склонность к математике. Этот метод также линеен по времени, поскольку в данном случае к стандартному поиску в глубину добавляется несколько операций, выполняющихся за постоянное время. ■