Связность в направленных графах - Графы

До настоящего момента мы рассматривали задачи, относящиеся к ненаправленным графам; теперь посмотрим, в какой степени эти идеи применимы к направленным графам.

Напомним, что в направленном графе ребро (и, v) имеет направление: оно проходит из и в v. В этом случае отношение между и и v является асимметричным, что имеет качественные последствия для структуры полученного графа. Например, в разделе 3.1 Всемирная паутина упоминалась как экземпляр большого, сложного направленного графа, узлами которого являются страницы, а ребрами — гиперссылки. Процесс веб-серфинга может быть представлен последовательностью ребер этого направленного графа; направленность важна, потому что в общем случае переход по гиперссылкам в обратном направлении невозможен.

В то же время многие базовые определения и алгоритмы имеют естественные аналоги в направленных графах. Например, к их числу относится представление списка смежности и алгоритмы поиска в графах, такие как BFS и DFS.

Представление направленных графов

Для представления направленных графов в контексте проектирования алгоритмов используется разновидность представления списка смежности, использовавшегося для ненаправленных графов. Вместо одного списка соседей в каждом узле хранятся два списка: один состоит из узлов, к которым ведут ребра от данного узла, а второй — из узлов, из которых выходят ребра к данному узлу. Таким образом, алгоритм, просматривающий узел и, может получить информацию как об узлах, достижимых при переходе на один шаг вперед по направленному ребру, так и об узлах, которые были бы достижимы при возврате на один шаг в обратном направлении (по ребру, ведущему к u).

Алгоритмы поиска

Алгоритмы поиска в ширину и в глубину в направленных графах почти не отличаются от аналогичных алгоритмов для ненаправленных графов. В этом разделе мы займемся BFS. Алгоритм начинает с узла s, определяет первый уровень из всех узлов, к которым ведет ребро из s, затем определяет второй уровень из всех узлов, к которым ведут ребра из узлов первого уровня, и т. д. При таком подходе узлы будут обнаруживаться уровень за уровнем в ходе распространения поиска от s, а уровень j будет состоять из узлов, для которых кратчайший путь из s содержит ровно j ребер. Как и в ненаправленном графе, этот алгоритм выполняет не более чем постоянный объем работы для каждого узла и ребра и поэтому работает за время O(m + n).

Важно понимать, что именно вычисляет направленная версия BFS. В направленных графах путь от узла s к t может существовать даже в том случае, если путь от t к s не существует; а направленная версия BFS вычисляет множество всех узлов t, обладающих тем свойством, что от 5 существует путь к t. От таких узлов могут существовать пути обратно к s, а могут и не существовать.

Для поиска в глубину тоже существует естественная аналогия, которая выполняется за линейное время и вычисляет то же множество узлов. В этом случае также используется рекурсивная процедура, которая пытается исследовать граф на максимально возможную глубину (на этот раз только по ребрам с соответствующим направлением). Когда DFS находится в узле и, он по порядку запускает рекурсивный поиск в глубину для каждого узла, к которому ведет ребро из u.

Допустим, для заданного узла s требуется получить множество узлов, от которых существуют пути к s (вместо узлов, к которым ведут пути из s). Это можно легко сделать, определив новый направленный граф G^rev, который получается из G простым изменением направления каждого ребра. После этого алгоритм BFS или DFS применяется к G^rev; путь из s к узлу существует в G^rev в том, и только в том случае, если в G существует путь из него в s.

Сильная связность

Вспомните, что направленный граф называется сильно связным, если для каждых двух узлов u и v существует путь из u в v и путь из v в u. Также полезно сформулировать некоторые термины для свойства, лежащего в основе этого определения; два узла u и v в направленном графе называются взаимодостижимыми, если существует путь из u в v и путь из v в u. (Таким образом, граф является сильно связным, если каждая пара узлов в нем взаимодостижима.)

Взаимодостижимость обладает рядом полезных свойств, многие из которых вытекают из следующего простого факта.

(3.16) Если узлы u и v являются взаимодостижимыми и узлы v и w являются взаимодостижимыми, то узлы u и w также являются взаимодостижимыми.

Доказательство. Чтобы построить путь от u к w, мы сначала перейдем от u к v (по пути, существование которого гарантируется взаимодостижимостью u и v), а затем от v к w (по пути, существование которого гарантируется взаимодостижимостью v и w). Для построения пути от w к u те же рассуждения применяются в обратном направлении: мы сначала перейдем от w к v (по пути, существование которого гарантируется взаимодостижимостью v и w), а затем от v к u (по пути, существование которого гарантируется взаимодостижимостью u и v).

Для проверки сильной связности направленного графа существует простой алгоритм с линейным временем выполнения, неявно базирующийся на (3.16). Мы выбираем любой узел s и проводим поиск BFS в G, начиная с s. Затем BFS выполняется от s в G^rev. Если хотя бы один из двух поисков не найдет все узлы, то очевидно, что G не является сильно связным. Но допустим, мы выяснили, что из s существует путь в каждый другой узел, и из каждого другого узла существует путь s. В этом случае s и v взаимодостижимы для каждого v, из чего можно сделать вывод о взаимодостижимости любых двух узлов u и v: s и u взаимодостижимы, s и v взаимодостижимы, и из (3.16) следует, что u и v также взаимодостижимы. ■

По аналогии с компонентами связности в ненаправленных графах мы можем определить сильную компоненту, содержащую узел s, для направленного графа как множество всех узлов v, для которых s и v является взаимодостижимыми. Если задуматься, алгоритм из предыдущего абзаца в действительности вычисляет сильную компоненту, содержащую s: мы выполняем BFS, начиная с s, в G и G^rev; множество узлов, достигнутых при обоих поисках, представляет собой множество узлов с путями в s и из s; следовательно, это множество является сильной компонентой, содержащей s.

На этом сходство между понятиями компоненты связности в ненаправленных графах и сильной компоненты в направленных графах не ограничивается. Вспомните, что компоненты связности образуют естественное разбиение графа, поскольку каждые две компоненты либо идентичны, либо изолированы. Сильные компоненты также обладают этим свойством, причем фактически по той же причине, следующей из (3.16).

(3.17) Для каждых двух узлов s и t в направленном графе их сильные компоненты либо идентичны, либо изолированны.

Доказательство. Возьмем два любых взаимодостижимых узла s и t; утверждается, что сильные компоненты, содержащие s и t, идентичны. В самом деле, для каждого узла v, если s и vвзаимодостижимы, то, согласно (3.16), t и v также взаимодостижимы. Аналогичным образом, если t и v взаимодостижимы, то, согласно (3.16), s и v также взаимодостижимы.

С другой стороны, если s и t не являются взаимодостижимыми, то не может быть узла v, входящего в сильную компоненту каждого из этих узлов. Если бы такой узел v существовал, то узлы s и v были бы взаимодостижимыми, узлы v и t были бы взаимодостижимыми, поэтому из (3.16) следовало бы, что s и t также являются взаимодостижимыми.

Хотя подробное обоснование здесь не приводится, при некоторой дополнительной работе возможно вычислить сильные компоненты всех узлов за общее время O(m + n). ■