2

数回前に投稿された解決策を見つけて、それを自分のエクササイズに適用しようとしましたが、うまくいきません。ノードとエッジを持つクラス グラフと、ノードのすべての子を与えるメソッド childrenOf があります。これはすべて正常に機能します。これは私の DFS 検索用のコードで、すべてのパスを見つけたいと考えています。

def myDFS(graph,start,end,path=[]):
path=path+[start]
if start==end:
    return path
paths=[]
for node in graph.childrenOf(start):
    if node not in path:
        paths.extend(myDFS(graph,node,end,path))            
return paths

空のリストしかありませんでした。どこを見る必要がありますか？ループで path=myDFS... を実行していたとき、少なくとも最後のパスがありました。path+=myDFS を試しましたが成功しませんでした。グラフは成功して作成されたので、そこから来ていません。ありがとう

4

2 に答える 2

6

最初から最後までのすべてのパスのみを取得する必要があるため、パスは最後に到達すると合計パス リストに追加されます。パスの全リストは返されませんが、入力されます。

paths = []

def myDFS(graph,start,end,path=[]): 
    path=path+[start] 
    if start==end:
        paths.append(path) 
    for node in graph.childrenOf(start):
        if node not in path:
            myDFS(graph,node,end,path)
于 2013-05-24T18:55:27.807 に答える