为有向图中的每个顶点查找可达顶点
Finding reachable vertices for every vertex in a directed graph
我知道执行此操作的蛮力方法是对 graph.So 的所有顶点执行 DFS 对于此算法，复杂度为 O(V|V+E|)。但是有没有更有效的方法来做到这一点？
[编辑：正如 kraskevich 所指出的，最终的查询步骤可能比我最初声称的更糟糕：即使对于大小为 O(|V|^2) 的输出也是如此|V|), 这并不比没有任何预处理的普通 DFS 好。].
在最坏的情况下，需要 O(|V|^2) space 来显式存储所有这些信息——即存储每个顶点的可到达顶点的完整列表（想想一个图，其中每个顶点都有到每个其他顶点的边）。但是可以用只需要 O(|V|) space 的方式来表示它，并且可以在 O(|V|+|E|) 时间内构建这种表示，并且对它的查询只会花费与答案大小成正比的时间（可到达的顶点数）.
基本思想是：strongly connected component（SCC）中的每个顶点都可以到达同一个SCC（这是SCC的定义）中的所有其他顶点，并且可以到达所有顶点在它可以到达的 SCC 中，没有其他顶点。
- 找到所有的SCC；这可以在 O(|V|+|E|) 时间内完成。构建一个table SCC，如果u的SCC为i，则SCC(u) = i（G和SCC中的顶点都可以表示为整数）。然后再通过这个 table 构建一个对偶 table 顶点，这样 Verts(i) 包含第 i 个 SCC 中所有顶点的列表。
- 构建一个新图 G'，其顶点是 G 的 SCC。G' 必然是无环的。
因此，给定 G 中的一个顶点 u，查找其 SCC，SCC(u)。称之为我。从顶点 i 开始通过 G' 执行 DFS：对于在此 DFS 期间遇到的每个顶点（G'）j，输出 Verts(j) 中的每个顶点（G）。
我真的怀疑没有已知的更好的通用图算法。我找到的关于主题 [1] [2] 的所有论文都描述了在 O(|V| * |E|) 时间内 运行 的算法。在最坏的情况下，这并不比您天真的尝试好。
甚至维基百科页面 [3] 也说最快的算法将问题简化为矩阵乘法，最快的算法只比您的基线好一点点。
[1] http://ion.uwinnipeg.ca/~ychen2/conferencePapers/tranRelationCopy.pdf
[2]http://www.vldb.org/conf/1988/P382.PDF
[3] http://en.wikipedia.org/wiki/Transitive_closure#Algorithms
我从像 http://research.microsoft.com/pubs/144985/todsfinal.pdf 这样的论文中得到的印象是，在一般情况下，没有比 O(VE) 或 O(V^3) 更好的算法。对于稀疏图和其他特殊图，有更快的算法。但是，如果您对将对数据进行的查询数量有一些了解，您似乎仍然可以通过将 "index construction" 与 "query" 分开来进行改进。如果要进行大量查询，如果所有数据都预先计算（DFS 或 Floyd-Warshall 等）并存储在 O(n^2) [=20= 中，则 O(1) 可以用于查询].另一方面，如果查询相对较少，space and/or 可以以查询时间为代价减少索引构建时间。
我知道执行此操作的蛮力方法是对 graph.So 的所有顶点执行 DFS 对于此算法，复杂度为 O(V|V+E|)。但是有没有更有效的方法来做到这一点？
[编辑：正如 kraskevich 所指出的，最终的查询步骤可能比我最初声称的更糟糕：即使对于大小为 O(|V|^2) 的输出也是如此|V|), 这并不比没有任何预处理的普通 DFS 好。].
在最坏的情况下，需要 O(|V|^2) space 来显式存储所有这些信息——即存储每个顶点的可到达顶点的完整列表（想想一个图，其中每个顶点都有到每个其他顶点的边）。但是可以用只需要 O(|V|) space 的方式来表示它，并且可以在 O(|V|+|E|) 时间内构建这种表示，并且对它的查询只会花费与答案大小成正比的时间（可到达的顶点数）.
基本思想是：strongly connected component（SCC）中的每个顶点都可以到达同一个SCC（这是SCC的定义）中的所有其他顶点，并且可以到达所有顶点在它可以到达的 SCC 中，没有其他顶点。
- 找到所有的SCC；这可以在 O(|V|+|E|) 时间内完成。构建一个table SCC，如果u的SCC为i，则SCC(u) = i（G和SCC中的顶点都可以表示为整数）。然后再通过这个 table 构建一个对偶 table 顶点，这样 Verts(i) 包含第 i 个 SCC 中所有顶点的列表。
- 构建一个新图 G'，其顶点是 G 的 SCC。G' 必然是无环的。
因此，给定 G 中的一个顶点 u，查找其 SCC，SCC(u)。称之为我。从顶点 i 开始通过 G' 执行 DFS：对于在此 DFS 期间遇到的每个顶点（G'）j，输出 Verts(j) 中的每个顶点（G）。
我真的怀疑没有已知的更好的通用图算法。我找到的关于主题 [1] [2] 的所有论文都描述了在 O(|V| * |E|) 时间内 运行 的算法。在最坏的情况下，这并不比您天真的尝试好。
甚至维基百科页面 [3] 也说最快的算法将问题简化为矩阵乘法，最快的算法只比您的基线好一点点。
[1] http://ion.uwinnipeg.ca/~ychen2/conferencePapers/tranRelationCopy.pdf
[2]http://www.vldb.org/conf/1988/P382.PDF
[3] http://en.wikipedia.org/wiki/Transitive_closure#Algorithms
我从像 http://research.microsoft.com/pubs/144985/todsfinal.pdf 这样的论文中得到的印象是，在一般情况下，没有比 O(VE) 或 O(V^3) 更好的算法。对于稀疏图和其他特殊图，有更快的算法。但是，如果您对将对数据进行的查询数量有一些了解，您似乎仍然可以通过将 "index construction" 与 "query" 分开来进行改进。如果要进行大量查询，如果所有数据都预先计算（DFS 或 Floyd-Warshall 等）并存储在 O(n^2) [=20= 中，则 O(1) 可以用于查询].另一方面，如果查询相对较少，space and/or 可以以查询时间为代价减少索引构建时间。