この回答で与えられた既存の非再帰的 DFS 実装は壊れているように見えるので、実際に機能するものを提供させてください。
私はこれを Python で書きました。かなり読みやすく、実装の詳細が整理されているためです (また、generatorsyieldを実装するための便利なキーワードがあるため)。ただし、他の言語への移植はかなり簡単なはずです。
# a generator function to find all simple paths between two nodes in a
# graph, represented as a dictionary that maps nodes to their neighbors
def find_simple_paths(graph, start, end):
visited = set()
visited.add(start)
nodestack = list()
indexstack = list()
current = start
i = 0
while True:
# get a list of the neighbors of the current node
neighbors = graph[current]
# find the next unvisited neighbor of this node, if any
while i < len(neighbors) and neighbors[i] in visited: i += 1
if i >= len(neighbors):
# we've reached the last neighbor of this node, backtrack
visited.remove(current)
if len(nodestack) < 1: break # can't backtrack, stop!
current = nodestack.pop()
i = indexstack.pop()
elif neighbors[i] == end:
# yay, we found the target node! let the caller process the path
yield nodestack + [current, end]
i += 1
else:
# push current node and index onto stacks, switch to neighbor
nodestack.append(current)
indexstack.append(i+1)
visited.add(neighbors[i])
current = neighbors[i]
i = 0
このコードは 2 つの並列スタックを維持します。1 つは現在のパスの以前のノードを含み、もう 1 つはノード スタック内の各ノードの現在の近隣インデックスを含みます (ノードをポップしたときに近隣ノードの反復処理を再開できるようにするため)。スタック)。(ノード、インデックス) ペアの 1 つのスタックを同様に使用することもできましたが、2 つのスタックの方法の方が読みやすく、おそらく他の言語のユーザーにとっては実装が簡単であると考えました。
このコードvisitedでは、現在のノードとスタック上のすべてのノードを常に含む別のセットも使用して、ノードが既に現在のパスの一部であるかどうかを効率的に確認できるようにします。スタックのような効率的なプッシュ/ポップ操作と効率的なメンバーシップ クエリの両方を提供する「順序付きセット」データ構造が言語にある場合は、それをノード スタックに使用して、個別のvisitedセットを取り除くことができます。
または、ノードにカスタムの可変クラス/構造を使用している場合は、各ノードにブール値フラグを格納して、現在の検索パスの一部としてアクセスされたかどうかを示すことができます。もちろん、この方法では、何らかの理由で同じグラフに対して 2 つの検索を並行して実行することはできません。
上記の関数がどのように機能するかを示すテストコードを次に示します。
# test graph:
# ,---B---.
# A | D
# `---C---'
graph = {
"A": ("B", "C"),
"B": ("A", "C", "D"),
"C": ("A", "B", "D"),
"D": ("B", "C"),
}
# find paths from A to D
for path in find_simple_paths(graph, "A", "D"): print " -> ".join(path)
与えられたサンプル グラフでこのコードを実行すると、次の出力が生成されます。
A -> B -> C -> D
A -> B -> D
A -> C -> B -> D
A -> C -> D
この例のグラフは無向 (つまり、すべての辺が双方向) ですが、このアルゴリズムは任意の有向グラフでも機能することに注意してください。たとえば、 (の隣接リストからC -> B削除することによって) エッジを削除すると、3 番目のパス ( ) を除いて同じ出力が得られますが、これはもはや不可能です。BCA -> C -> B -> D
Ps。このような単純な検索アルゴリズム (およびこのスレッドで提供されている他のアルゴリズム) のパフォーマンスが非常に低いグラフを作成するのは簡単です。
たとえば、無向グラフで A から B へのすべてのパスを検索するタスクを考えます。この場合、開始ノード A には 2 つの隣接ノードがあります。ターゲット ノード B (A 以外の隣接ノードはありません) と、クリークの一部であるノード C です。 n +1 ノードの場合、次のようになります。
graph = {
"A": ("B", "C"),
"B": ("A"),
"C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),
"H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),
"I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),
"J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),
"K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),
"L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),
"M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),
"N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),
"O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),
}
A と B の間の唯一のパスが直接パスであることは簡単にわかりますが、ノード A から開始されたナイーブな DFS は、クリーク内のパスを無駄に探索するために O( n !) 時間を無駄にします。これらのパスのいずれも B につながる可能性はありません。
同様のプロパティを持つDAGを構築することもできます。たとえば、開始ノード A をターゲット ノード B に接続し、他の 2 つのノード C 1および C 2に接続します。これらのノードは両方ともノード D 1および D 2に接続し、両方ともノード E に接続します。1と E 2など。このように配置されたn層のノードの場合、A から B へのすべてのパスを単純に検索すると、O(2 n ) の時間が無駄になり、あきらめる前にすべての行き止まりを調べることになります。
もちろん、(C 以外の) クリーク内のノードの 1 つから、または DAG の最後の層からターゲット ノード B にエッジを追加すると、A から B への指数関数的に多数の可能なパスが作成されます。純粋にローカルな検索アルゴリズムでは、そのようなエッジが見つかるかどうかを事前に知ることはできません。したがって、ある意味では、このような素朴な検索の出力感度が低いのは、グラフのグローバル構造に対する認識の欠如によるものです。
これらの「指数時間のデッドエンド」のいくつかを回避するために使用できるさまざまな前処理方法（リーフノードを繰り返し削除する、単一ノードの頂点セパレーターを検索するなど）がありますが、一般的な方法は知りません。すべての場合にそれらを排除できる前処理トリック。一般的な解決策は、検索のすべてのステップでターゲット ノードがまだ到達可能かどうかを確認し (サブサーチを使用)、到達可能でない場合は早期にバックトラックすることですが、悲しいことに、検索が大幅に遅くなります (最悪の場合、 、グラフのサイズに比例する)などの病理学的行き止まりを含まない多くのグラフ。