Введение
Можно ли достичь одной вершины из другой в графе?
В теории графов, достижимость относится к возможности перехода от одной вершины к другой внутри графа. Вершина может достигать вершины (и достижима из ) если существует последовательность смежных вершин (то есть путь), начинающаяся в и заканчивающаяся в . В неориентированном графе достижимость между всеми парами вершин можно определить, выявив связные компоненты графа. Любая пара вершин в таком графе может достигать друг друга тогда и только тогда, когда они принадлежат одному и тому же связному компоненту; следовательно, в таком графе достижимость симметрична ( достигает , если и только если достигает ). Связные компоненты неориентированного графа можно определить за линейное время. Остальная часть статьи посвящена более сложной задаче определения попарной достижимости в ориентированном графе (который, кстати, не обязательно должен быть симметричным).
In an undirected graph, reachability between all pairs of vertices can be determined by identifying the connected components of the graph. Any pair of vertices in such a graph can reach each other if and only if they belong to the same connected component; therefore, in such a graph, reachability is symmetric ( reaches iff reaches ). The connected components of an undirected graph can be identified in linear time. The remainder of this article focuses on the more difficult problem of determining pairwise reachability in a directed graph (which, incidentally, need not be symmetric).
Определение
Для ориентированного графа , с множеством вершин и множеством ребер , отношение достижимости из – это транзитивное замыкание , то есть множество всех упорядоченных пар вершин в , для которых существует последовательность вершин , такая что ребро принадлежит для всех . Если граф ацикличен, то его отношение достижимости является частичным порядком; любой частичный порядок может быть определен таким образом, например, как отношение достижимости его транзитивного сокращения. Важным следствием этого является то, что поскольку частичные порядки антисимметричны, если вершина может достичь вершину , то мы знаем, что вершина не может достичь . Интуитивно, если бы можно было пройти из в и обратно в , то граф содержал бы цикл, что противоречит его ацикличности. Если граф ориентированный, но не ацикличен (то есть содержит по крайней мере один цикл), то его отношение достижимости будет соответствовать предзаказу, а не частичному порядку.
If is acyclic, then its reachability relation is a partial order; any partial order may be defined in this way, for instance as the reachability relation of its transitive reduction. A noteworthy consequence of this is that since partial orders are anti symmetric, if can reach , then we know that cannot reach Intuitively, if we could travel from to and back to , then would contain a cycle, contradicting that it is acyclic. If is directed but not acyclic (i. e. it contains at least one cycle), then its reachability relation will correspond to a preorder instead of a partial order.
Алгоритмы
Алгоритмы определения достижимости делятся на два класса: те, которые требуют предварительной обработки, и те, которые не требуют её. Если необходимо выполнить только один (или несколько) запросов, может оказаться более эффективным не использовать сложные структуры данных и вычислить достижимость нужной пары напрямую. Это можно сделать за линейное время, используя такие алгоритмы, как поиск в ширину или итеративное углубление поиска в глубину. Если планируется выполнять множество запросов, то можно применить более сложный метод; конкретный выбор метода зависит от структуры анализируемого графа. В обмен на время предварительной обработки и дополнительное место для хранения, можно создать структуру данных, которая затем сможет отвечать на запросы о достижимости для любой пары вершин за время, не превышающее . Ниже описаны три различных алгоритма и структуры данных для трех различных, постепенно усложняющихся ситуаций.
Алгоритм Флойда-Уоршалла
Алгоритм Флойда — Уоршалла может быть использован для вычисления транзитивного замыкания любого ориентированного графа, что позволяет определить отношение достижимости, как указано в определении выше. В худшем случае алгоритм требует времени и памяти. Этот алгоритм не ограничивается только определением достижимости, поскольку он также вычисляет расстояние кратчайшего пути между всеми парами вершин. Для графов, содержащих отрицательные циклы, кратчайшие пути могут быть не определены, однако достижимость между парами вершин все равно можно установить.
Связанные проблемы
Связанная проблема — решение задач на достижимость при заданном количестве вышедших из строя вершин. Например: "Может ли вершина `v` достичь вершины `u`, даже если вершины `x`, `y` и `z` вышли из строя и больше не могут использоваться?" Аналогичная задача может рассматривать выход из строя рёбер вместо вершин, или их комбинацию. Алгоритм поиска в ширину также эффективно работает для таких задач, но построение эффективного оракула представляет собой более сложную задачу. Другой аспект, связанный с задачами на достижимость, — это быстрое пересчитывание изменений в отношениях достижимости при изменении части графа. Например, это актуально для сборщика мусора, которому необходимо сбалансировать освобождение памяти (для последующего перераспределения) и требования к производительности работающего приложения.