Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Глава 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) для читателей, имеющих склонность к математике. Этот метод также линеен по времени, поскольку в данном случае к стан­дартному поиску в глубину добавляется несколько операций, выполняющихся за по­стоянное время. ■






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.