计算邻接表中每个顶点的可达性

Question

给定 DAG 的邻接表 Map<Vertex, Set<Vertex>>，我想计算每个顶点的可达性（即是否存在从 u 到 v 的路径）。

static Map<Vertex, Set<Vertex>> reachability(Map<Vertex, Set<Vertex>> adjList) {}

我知道可以在 O(V^3)

中使用 Floyd-Warshall

// 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];
}

但是我有一个稀疏图（和一个邻接表），那么最快的方法是什么？

Answer 1

O(V*(V+E)) 解决方案可能是从图中的每个节点执行简单的 BFS 并计算其可达性集。假设 |E| << |V|^2（你说图形是稀疏的），这比 floyd-warshall 快得多（并且更容易编码）。

然而，这仍然不是最理想的，并且可以改进：

你的图是一个 DAG，所以你可以先在 O(V+E) 中做一个 topological sort，然后，从最后到第一：

连接（v）=联合{连接（u）|对于所有边 (v,u) } U {v}

这可以非常有效地计算，并在时间复杂度上为您提供完整的答案 O(|V|+|E|+k) 其中 |V| - 顶点数，|E| - 边的数量，k - 连接对的数量（在最坏的情况下限制为 O(|V|^2)）。

此解决方案为您提供 O(|V|^2) 最坏情况下的性能，即使对于 none 稀疏图也是如此。

伪代码：

V = [v0,v1,...,vn-1]
V = topological_sort(V) //O(V+E)
connect = new Map:V->2^V //Map<Vertex,Set<Vertex>> in java
i = n-1
while (i >= 0):
   let v be the vertex in V[i]
   connected[v].add(v)
   for each edge (v,u):
      //since the graph is DAG, and we process in reverse order
      //the value of connected[u] is already known, so we can use it.
      connected[v].addAll(connected[u])

Answer 2

这是一个简单的 O(|V||E|) Scala 解决方案（基本上，对每个顶点，做一个 DFS）：

type AdjList[A] = Map[A, Set[A]]

def transitiveClosure[A](adjList: AdjList[A]): AdjList[A]  = {
  def dfs(seen: Set[A])(u: A): Set[A] = {
    require(!seen(u), s"Cycle detected with $u in it")
    (adjList(u) filterNot seen flatMap dfs(seen + u)) + u
  }
  adjList.keys map {u =>
    u -> dfs(Set.empty)(u)  
  } toMap
}

可执行版本在这里：http://scalafiddle.net/console/4f1730a9b124eea813b992edebc06840

计算邻接表中每个顶点的可达性

Calculate reachability for every vertex from adjacency list

algorithm

graph-theory

graph-algorithm

floyd-warshall

transitive-closure