Главная » Java, Структуры данных и алгоритмы » Обход диграфа

0

Как и в случае с ненаправленным графом, систематизируем диграф с помощью методов, аналогичных алгоритмам DFS и BFS (п. 12.3.1 и 12.3.2) и отличающихся только тем, что движение в них совершается согласно направлениям путей диграфа.

Направленная версия DFS-алгоритма, начинающего работу в узле v, * может быть описана рекурсивным алгоритмом из фрагмента кода 12.9 (см. рис. 12.9).

Алгоритм DirectedDFS(v):

Отметка узла v как пройденного.

for каждого выходящего пути (v,w) узла у do if узел w еще не пройден then

рекурсивный вызов DirectedDFS(w).

Фрагмент кода 12.9. Алгоритм DirectedDFS

DFS в диграфе G делит пути диграфа, достижимые из стартовой точки, на пути дерева (tree edge), или открывающие пути, ведущие к еще не пройденным узлам, и недревесные пути (nontree edge), ведущие к уже пройденным узлам. Пути дерева формируют дерево, называемое деревом

Рис. 12.9. Пример DFS в диграфе: (а) переходная стадия, где впервые достигается уже Пройденный узел (DFW); (Ь) законченный DFS. Пути дерева отмечены линиями с длинным штрихом, обратные пути — линиями с точечным штрихом, а прямые и поперечные пути — сплошными линиями. Порядок прохождения узлов указан маркировкой узла. Путь (ORD,DFW) является обратным, a (DFW,ORD) — прямым. Путь (BOS,SFO) — прямой, a (SFO,LAX) — поперечный

поиска в глубину, корнем которого является узел отправления. Недревесные пути подразделяются на три группы:

•   обратные пути, соединяющие узел с предшественником в DFS-дереве;

•   прямые пути, соединяющие узел с потомком в DFS-дереве;

•      поперечные пути, соединяющие узел с узлом, не являющимся ни его предшественником, ни потомком.

Вернемся к рисунку 12.9, b и рассмотрим пример недревесных путей.

Утверждение 12.9. Пусть G будет диграфом, в котором выполняется поиск в глубину, начинающийся из узла s. Поиск обходит все узлы G, достижимые из s. Кроме того, DFS-дерево содержит направленные маршруты от я до каждого достижимого из него узла.

Доказательство. Пусть Vs будет подмножеством узлов С, проходимых DFS-алгоритмом, начиная с s. Требуется доказать, что Vs состоит из s и всех достижимых из s узлов. Докажем от противного, что существует узел v, достижимый из s, но не входящий в Vs. Рассмотрим направленный маршрут из s в v, где (u,v) будет первым путем этого маршрута, выходящим из Vs, то есть и входит в Vs, a v не входит в Vs. При достижении алгоритмом DFS узла и исследуются все исходящие из него пути и, таким образом, должен быть достигнут и узел v через путь (u,v). Следовательно, v должен входить в Vs. Таким образом, Vs должен содержать каждый узел, достижимый из s.

Анализ времени выполнения направленного DFS-метода аналогичен анализу его ненаправленного прототипа. В частности, рекурсивный вызов выполняется для каждого узла только один раз, и каждый путь проходится только один раз (из места его отправления). Следовательно, если ns узлов и ms путей достижимы из узла s, направленный поиск в глубину, берущий начало в s, выполняется за 0(п + т) времени, при условии, что диграф реализован Структурой* поддерживающей методы работы с узлами и путями, имеющими пропорциональное 0(1) время выполнения. Например, структура списка смежности отвечает этому условию.

Согласно утверждению 12.8, можно использовать DFS для поиска узлов, достижимых из конкретного узла, и, соответственно, поиска транзитивного замыкания диграфа б. Это означает, что поиск может выполняться в глубину, начиная с любого узла v в G, с тем чтобы выяснить, какие узлы w достижимы из v, добавляя путь (v,w) в транзитивное замыкание для каждого такого w. Аналогично при многократном обходе диграфа с помощью DFS, началом которого будут разные узлы, легко определится, присуща ли G строгая связаность. А именно, G будет строго связанным, если каждый обход проходит через все узлы G. Это порождает следующее утверждение.

Утверждение 12.10. Пусть б будет диграфом из п узлов и т путей. Алгоритм DFS обходит б п раз, выполняется за 0(п + т) времени, требует О(п) дополнительного пространства и может решать следующие задачи:

•               для каждого узла v в б вычислить подграф достижимых узлов; • • проверить, является ли б строго связанным;

•               вычислить транзитивное замыкание G* диграфа б.

Проверка строгого связывания

Определить, является ли б строго связанным, можно достаточно просто, воспользовавшись двумя заходами поиска в глубину. Начинаем с запуска DFS в произвольном узле s. При наличии в б хотя бы одного непройденного узла, не достижимого из s, диграф не является строго связным. Если при первом обходе все узлы в б оказываются пройденными, то с помощью метода reverseDirection изменяем направления путей и снова запускаем DFS из в зеркальном отражении диграфа. Если и в этом случае все узлы в б будут пройдены, то диграф строго связанный, так как каждый узел, пройденный в этом поиске, может достичь s. Поскольку этот алгоритм осуществляет всего два обхода диграфа б, то выполняется он за 0(п + т) времени.

Направленный поиск в ширину

Как и при поиске в глубину, расширим возможности поиска в ширину (BFS) для работы с направленными графами. Алгоритм так же будет обходить все узлы, уровень за уровнем, и делить множество путей на пути, образующие дерево направленного поиска в ширину, растущее из стартового узла, и недревесные пути. Но, в отличие от направленного поиска в глубину, направленный поиск в ширину имеет только два типа недревесных путей: обратные пути, соединяющие узел с одним из его предшественников, и поперечные пути, соединяющие узел с другим узлом, не являющимся ни предшественником, ни потомком данного узла. В этом методе нет прямых путей, и это читатель может установить, выполнив упражнение 3-12.9.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии