1

次の形式のデータベースにデータがあります。

A -> B
C -> D
B -> C
F -> G
G -> J
X -> Z

これは基本的に、A が B に移動し、C が D に移動するなどを意味します。このデータとノード (C など) を考えると、 A -> B -> C -> D である C が見つかった完全なパスを構築したいと思います。 . いくつかの辞書と再帰ループを使用してこれを実行しようとしましたが、db には大量のデータがあるため、このような遅いソリューションは好きではありません。この問題を解決するより良い方法は何ですか? アルゴリズムとデータ構造の両方に関して？アイデアやヒントをいただければ幸いです。

4

1 に答える 1

2

基本的にDFSを探していますが、方向ごとに 2 回実行する必要があります。

まず、Cから始めて、逆の「グラフ」でDFSを実行し ます。
あなたの例では、Path1 = C->B->A

次に、再び C から、元のグラフで DFS を実行し
ます。例では、次のようになります。Path2= C->D

を逆Path1にして連結Path2すると、次のようになります。

reverse(Path1)  + Path2 = A->B->C + C->D = A->B->C->D

明確化-DFSは単なる抽象化であり、実際に行っていることは(疑似コード)に似ています:

current <- C
list = []
while (current != null):
   list.addFirst(current)
   current <- u such that (u,current) is in the DataBase
current <- C
list.deleteLast() // last is C
while (current != null):
   list.addLast(current)
   current <- u such that (current,u) is in the DataBase

両方のケースを見つけるには、単純な辞書検索が必要であることに注意してくださいu。最初の「ターゲット」がキーで、2 番目の「ソース」がキーです。

于 2013-01-28T14:12:45.143 に答える