4

私の特定のケースでは、グラフは隣接リストとして表され、無向でスパースです。nは数百万単位で、dは3です。A^ d（Aは隣接行列）を計算し、ゼロ以外を選択します。エントリは機能しますが、行列の乗算を含まないものが必要です。すべての頂点の幅優先探索もオプションですが、時間がかかります。

4

4 に答える 4

1 
def find_d(graph, start, st, d=0):

    if d == 0:
        st.add(start)
    else:
        st.add(start)
        for edge in graph[start]:
            find_d(graph, edge, st, d-1)

    return st

graph = { 1 : [2, 3],
      2 : [1, 4, 5, 6],
      3 : [1, 4],
      4 : [2, 3, 5],
      5 : [2, 4, 6],
      6 : [2, 5]
    }

print find_d(graph, 1, set(), 2)
于 2013-10-11T18:05:53.760 に答える
0

を計算するオプションについてはすでに言及していますがA^d、これは必要以上のものです（すでに述べたように）。

ただし、このアイデアを使用するはるかに安価な方法があります。v一連の頂点を表すゼロと 1の (列) ベクトルがあるとします。ベクトルw := A vには、ちょうど 1 ステップで開始ノードから到達できるすべてのノードに 1 が含まれるようになりました。繰り返し、u := A wちょうど2つのステップで開始ノードから到達できるすべてのノードに1つあります。

の場合d=3、次のことができます (MATLAB 疑似コード)。

v = j'th unit vector
w = v
for i = (1:d)
   v = A*v
   w = w + v
end

ベクトルには、最大ステップで th ノードwからアクセスできる各ノードの正のエントリがあります。jd

于 2011-04-19T11:25:41.417 に答える
0

vertexverticesWithin(d,x)の距離内にあるすべての頂点を見つける関数があるとします。dx

このような問題に対して、キャッシング/メモ化の機会を明らかにする良い戦略の 1 つは、次の質問をすることです:この問題のサブ問題は互いにどのように関連していますか?

verticesWithin(d,x)この場合、 ifは範囲内のfor alld >= 1の結合であることがわかります。ここで. もしそうなら、それは単純です。(頂点はそれ自体からの距離が 0 であると見なされると想定しています。)vertices(d-1,y[i])iy=verticesWithin(1,x)d == 0{x}

d == 1実際には、無限ループを避けるために、その関係を使用するのではなく、 case の隣接リストを確認する必要があります。xまた、自分自身を のメンバーとみなす冗長性を避ける必要がありますy。

また、 の戻り値の型がverticesWithin(d,x)単純なリストまたはセットdから、 からの距離の増加を表すセットのリストに変更されたx場合、

verticesWithin(d,x) = init(verticesWithin(d+1,x))

whereinitは、リストの最後の要素を除くすべての要素を生成する関数です。明らかに、これを文字通りコードに書き写すと、非終了の再帰関係になるため、実装方法について少し賢くする必要があります。

サブ問題間のこれらの関係を装備すると、 の結果をキャッシュし、verticesWithinこれらのキャッシュされた結果を使用して、冗長なトラバーサルの実行を回避できます (ただし、いくつかのセット操作を実行するコストがかかりますが、これが勝利であるかどうかは完全にはわかりません)。実装の詳細を記入する演習として残します。

于 2011-04-16T09:12:15.943 に答える
0

この場合、指定された頂点から始まる幅優先探索が最適なソリューションです。距離 d 内にあるすべての頂点が見つかり、距離 >= d + 2 の頂点にアクセスすることさえありません。

これは再帰コードですが、再帰は必要に応じてキューを使用して簡単に取り除くことができます。

// Returns a Set
Set<Node> getNodesWithinDist(Node x, int d)
{
  Set<Node> s = new HashSet<Node>();  // our return value
  if (d == 0) {
    s.add(x);
  } else {
    for (Node y: adjList(x)) {
       s.addAll(getNodesWithinDist(y,d-1);
    }
  }
  return s;
}
于 2011-04-19T11:56:57.097 に答える