Вопрос:
Я знаю, что подход грубой силы для этого выполняет DFS во всех вершинах графа. Поэтому для этого алгоритма сложность будет O (V | V + E |). Но есть ли более эффективный способ сделать это?
Лучший ответ:
Я получаю впечатление от таких документов, как http://research.microsoft.com/pubs/144985/todsfinal.pdf, что нет алгоритма, который лучше, чем O(VE) или O(V^3) в общий случай. Для разреженных графиков и других специальных графиков существуют более быстрые алгоритмы. Кажется, однако, что вы все еще можете улучшить, отделив “конструкцию индекса” от “запроса”, если у вас есть представление о количестве запросов, которые будут сделаны в данных. Если будет много запросов, O(1) возможен для запросов, если все данные предварительно вычисляются (DFS или Floyd-Warshall и т.д.) И сохраняются в пространстве O(n^2). С другой стороны, если будет относительно мало запросов, время построения пространства и/или индекса может быть уменьшено за счет времени запроса.
Ответ №1
Я действительно подозреваю, что нет известного лучшего алгоритма для общих графиков. Все документы, которые я нашел по этому вопросу [1] [2], описывают алгоритмы, которые работают в O (| V | * | E |). Это не лучше вашей наивной попытки в худшем случае.
Даже на странице wikipedia [3] говорится, что самые быстрые алгоритмы уменьшают проблему до матричного умножения, причем самые быстрые алгоритмы только немного лучше, чем исходные.
[1]
[2] http://www.vldb.org/conf/1988/P382.PDF
[3] http://en.wikipedia.org/wiki/Transitive_closure#Algorithms
Ответ №2
[РЕДАКТИРОВАТЬ: Как отметил Крaскевич, конечный шаг запроса может быть хуже, чем я изначально утверждал: до O (| V | ^ 2) даже для вывода размера O (| V |), что не лучше, чем обычная DFS без предварительной обработки.].
В худшем случае потребуется пространство O (| V | ^ 2), чтобы хранить всю эту информацию явно, т.е. хранить полный список достижимых вершин для каждой вершины (подумайте о графе, в котором каждая вершина имеет ребро для каждой другой вершины). Но можно представить его таким образом, что требуется только пространство O (| V |), и это представление может быть построено в O (| V | + | E |) time, , и запрос на него будет только время, пропорциональное размеру ответа (количество достижимых вершин).
Основная идея: Каждая вершина в сильно подключенном компоненте (SCC) может достигать любой другой вершины в том же SCC ( это определение SCC) и может достигать всех вершин в SCC, которые он может достичь, и других вершин.
- Найти все SCC; это можно сделать в O (| V | + | E |). Создайте таблицу SCC, так что SCC (u) = i, если SCC из u is я (обе вершины в G и SCC могут быть представлены целыми числами). Затем проделайте еще один проход через эту таблицу, чтобы создать двойную таблицу Verts, так что Verts (i) содержит список всех вершин в i-м SCC.
- Построим новый граф G ‘, вершины которого являются SCC G. G’ обязательно будут ациклическими.
Итак, учитывая вершину u в G, найдите ее SCC, SCC (u). Назовите это i. Выполните DFS через G ‘, начиная с вершины i: для каждой вершины (из G’) j, встречающейся во время этой DFS, выведите каждую вершину (из G) в Verts (j).
