0

これをJavaでコーディングしようとしています。このシナリオで機能するアルゴリズムを提案してください。入力は次のとおりです。

Col A   Col B
A       B
A       C
B       D
C       A
C       B
C       E
D       A
D       B
E       A

出力などの組み合わせを作成しようとしています:

A   B   D   A       
A   C   A           
A   C   B   D   A   
A   C   E   A       
B   D   B           
C   A   B   D   A   C
C   A   C           
C   B   D   A   C   
C   E   A   C

|
|
|

等々。出力には、開始点と終了点が同じである必要があります。

別の見方をすると、ノード A から開始し、ノード A に戻る必要があるため、パスは A から B、次に B から D になります (B からは 1 つのノードにしか移動できないため、つまりD)、次に D から A へ。したがって、col A と Col B は可能なパスを示します。たとえば、A からは B と C にのみ移動でき、D と E には移動できません。これが役立つことを願っています。また、番号を制限する方法はありますか。解決のためのノードの数?

いくつかのアイデアを提案してください。

4

2 に答える 2

0

データから、A、B、C、D、およびEの5つの異なるノードのコレクションがあります。

それらを組み合わせると、何が何に関連するかのマッピングが得られます。

A:  [B, C]
B:  [D]
C:  [B, E]
D:  [A, B]
E:  [A]

上記はスパースグラフを表しています。B-> D-> Bを除いて、ノードは別のノードからそれ自体に直接接続しません。

これが私がそれにアプローチする方法のフロープロセスです。

  • Map<String, List<String>到達するプライマリノードと、このノードが接続されているエッジにを使用します。

  • 開始ノードを選択します。リンクをスタックに配置します。

  • 終了ノードが開始ノードと同じであるかどうかを確認します。
    • そうである場合は、これで完了です。スタックから要素をポップして、パスを取得します。
    • そうでない場合は、スタックから最初の要素をポップし、そのリンクをスタックにプッシュします。チェックから繰り返します。
  • ポップするものがない場合、aから。へのパスはありません。

このスタイルのトラバーサルは、深さ優先探索です。パスに到達するか、オプションを使い果たすまで、グラフをさらに深く掘り下げていきます。

于 2013-03-17T20:23:28.130 に答える
0

再帰を使用する必要があり、データを再帰するときに、同じパスを無限に歩かないように、訪れた場所をマークする必要があります。

于 2013-03-17T20:13:06.760 に答える