1

無向で重みのないグラフで、長さが 1,2,..,n (n はユーザー定義の値) の接続されたノードのすべてのグループを列挙するにはどうすればよいですか?

この質問はこれに似ています。この違いにより: n=3 の場合。また、ABC と CEF というパスを見つける必要があります。

n が 4 の場合、パスには以下も含まれている必要があります。

あいうえお

ABCE

ABCF

ACEF

これは次のような問題だと思います。「すべてのペア - すべてのパス」。各パスには最大 n ノードを含めることができます。メソッドの計算の複雑さも教えてください。

私の考えでは、DFS と BFS の両方を同時に使用する必要がありますが、これが効率的かどうかはわかりません。

4

1 に答える 1

0

基本的に、の再帰に渡される追加の変数を使用して DFS を使用できlengthます。これは、反復ごとに削減されます。この余分な変数が 0 になったときが停止条件になります。

次のようなもの：

DFS(source,length,path):
   print path //this is always done, because we want all paths up to n
   if (length == 0): //stop clause
      return
   for each (source,u) is an edge:
       path.append(u)
       DFS(u,length-1,path)
       path.removeLast() //clean up environment

もう1つ（効率は劣りますが、よりエレガントかもしれません）は、 length=1,2,...,n でIterative Deepening DFSを実行しています（そして、停止句のみに出力を入れます）

于 2013-01-09T14:48:13.910 に答える