给定一个 DAG 的邻接列表Map<Vertex, Set<Vertex>>
,我想计算每个顶点的可达性(即是否存在从 u 到 v 的路径)。
static Map<Vertex, Set<Vertex>> reachability(Map<Vertex, Set<Vertex>> adjList) {}
我知道使用 Floyd-Warshall 是可能的O(V^3)
// Convert adjList to adjacency matrix mat
void reachability(boolean mat[][]) {
final int N = mat.length;
for (int k = 0; k < N; k++)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
mat[i][j] |= mat[i][k] && mat[k][j];
}
但是我有一个稀疏图(和一个邻接表),那么最快的方法是什么?