無向巡回グラフが与えられた場合、幅優先探索または深さ優先探索を使用して、可能なすべてのトラバーサルを見つけたいと考えています。それは隣接リストとしてグラフを与えられます:
A-BC
B-A
C-ADE
D-C
E-C
したがって、ルート A からのすべての BFS パスは次のようになります。
{ABCDE,ABCED,ACBDE,ACBED}
DFS の場合:
{ABCDE,ABCED,ACDEB,ACEDB}
これらのトラバーサルを意味のある方法でアルゴリズム的に生成するにはどうすればよいですか? 文字のすべての順列を生成してその有効性をチェックできると思いますが、それは最後の手段のように思えます。
どんな助けでも大歓迎です。
BFS は非常に単純である必要があります。各ノードには、それが見つかる特定の深度があります。あなたの例では、深さ0でA、深さ1でBとC、深さ2でEとDを見つけます。各BFSパスでは、最初の要素として深さ0（A）の要素があり、その後に任意の順列が続きます深さ 1 の要素 (B および C)、続いて深さ 2 の要素の順列 (E および D) など...例を見ると、4 つの BFS パスがそのパターンに一致します。A は常に最初の要素で、その後に BC または CB、その後に DE または ED が続きます。より深い深さにノードを持つグラフに対してこれを一般化できます。それを見つけるために必要なのは、非常に安価な 1 つの Dijkstra 検索だけです。
DFS では、BFS を簡単にする深さによる適切な分離がありません。上記のアルゴリズムほど効率的なアルゴリズムはすぐには見つかりません。グラフ構造を設定し、グラフをトラバースしてバックトラックすることでパスを構築できます。これがあまり効率的でない場合もありますが、アプリケーションには十分な場合があります。
可能なすべての DFS および BFS トラバーサルを実際に実行する明白な方法とは別に、次のアプローチを試すことができます。
ステップ 1. ルート A から始まる dfs トラバーサルでは、現在訪問しているノードの隣接リストを次のように変換します。まず、リストからノードの親を削除します。次に、adj リスト内の残りのノードの順列をすべて生成します。
したがって、ノード A からノード C にいる場合は、次のようにします。
C -> ADE transform into C -> DE transform into C -> [DE, ED]
ステップ 2. ステップ 1 の後、次の変換された adj リストが得られます。
A -> [CB, BC]
B -> []
C -> [DE, ED]
D -> []
E -> []
次に、(A,0) から始まる処理を開始します。ペアの最初の項目はトラバーサル パスで、2 番目の項目はインデックスです。2 つのキューがあるとします。BFS キューと DFS キュー。このペアを両方のキューに入れます。
ここで、最初に 1 つのキューが空になるまで次の手順を繰り返し、次にもう 1 つのキューに対して繰り返します。
最初のペアをキューから取り出します。(A,0) を取得します。ノード A は [BC, CB] にマップされます。したがって、2 つの新しいパス (ACB,1) と (ABC,1) を生成します。これらの新しいパスをキューに入れます。
これらの最初の 1 つをキューから取り出して (ACB,1) を取得します。インデックスは 1 なので、パス文字列の 2 番目の文字を調べます。これは C です。ノード C は [DE, ED] にマップされます。
上記に基づいて、作業しているキューに従って新しいパスを生成し、それらをキューに入れます。したがって、BFS キューで作業している場合は、(ACBDE,2) と (ACBED,2) を入力します。キューの内容は、(ABC,1)、(ACBDE,2)、(ACBED,2) です。
(ABC,1) をキューからポップします。B には子がないため、(ABC,2) を生成します。キューを取得します: (ACBDE,2)、(ACBED,2)、(ABC,2) など。ある時点で、インデックスがパスに含まれていない一連のペアになってしまいます。たとえば、(ACBED,5) が得られた場合、これが完成したパスであることがわかります。