0

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

しかし、私はスパース グラフ (および隣接リスト) を持っているので、これを行うための最速の方法は何ですか?

4

2 に答える 2

2

解決策は、グラフ内のすべてのノードからO(V*(V+E))単純なBFSを実行し、その到達可能性セットを計算することです。（グラフがまばらだと言った）と仮定すると|E| << |V|^2、これは floyd-warshall よりも大幅に高速です（そしてコーディングが簡単です）。

ただし、これはまだ最適ではなく、改善することができます。

グラフは DAG であるため、最初に でトポロジカル ソートを実行してO(V+E)から、最後から最初に移動できます。

接続 (v) = ユニオン { 接続 (u) | すべての辺 (v,u) } U {v}

O(|V|+|E|+k)これは非常に効率的に計算でき、|V|である時間計算量で合計の答えが得られます。- 頂点の数 |E| - エッジの数、k - 接続されたペアの数 (O(|V|^2)最悪の場合に制限されます)。

このソリューションはO(|V|^2)、疎なグラフがない場合でも、最悪の場合のパフォーマンスを提供します。

擬似コード:

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])
于 2015-07-14T22:08:18.127 に答える
0

Scalaでの簡単なO(|V||E|)解決策を次に示します (基本的に、頂点ごとに 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

于 2015-07-16T17:56:10.543 に答える