0

ノード「A」から始まり、同じノードで終わるすべての可能なパスを取得することに取り組んでいます。グラフは有向グラフです (つまり、各ノードは少なくとも 1 つのノードに接続されます)。

制約は次のとおりです。(もちろん開始ノード)を除いて、ノードに一度だけアクセスできます。

問題 : MATLAB で graphraverse 関数を使用してこれを実装しようとしましたが、そのような方法は 1 つしかありません。C、Java で実装できる任意のアルゴリズムまたはロジックが機能します。

誰かが私にそれへの指針を与えることができればうれしいです.

注: 最短パスは必要ありません。可能なパスのセットが必要です。

4

2 に答える 2

1

独自の再帰関数を作成してみませんか?

findPath(Node start, Node end, List<Node> alreadyVisited)
    for (Node neighbor: other ends of outgoing edges from start) { 
         if (neighbor == end)
             display("Found a path: " + alreadyVisited + end)
         else if (neighbor not in alreadyVisited)
             findPath(neighbor, end, alreadyVisited + neighbor)
    }

...または似たようなもの。サイクルを探すので、最初の呼び出しでは と に同じ値を渡す必要がstartありendます。もちろん、プロンプトへの出力が十分でない場合は、正しいパスをグローバル配列に収集するか、それらを返すより洗練された方法を見つける必要があります。

また、双方向検索を行う (入力エッジを同時にたどり、目的の終点に到達したかどうかだけでなく、連続する出力エッジと連続する入力エッジが到達するノードの交点をチェックする) 方が、グラフが大きいほど高速になります。

于 2012-06-11T09:52:32.723 に答える
0

あなたのレベルはわかりませんが、正しく構成できればブーストライブラリは非常に優れています

于 2012-06-11T07:57:49.763 に答える