2

このコードは、グラフ理論に関するPythonの公式エッセイに記載されています。コードは次のとおりです。

def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if not graph.has_key(start):
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths

私はまだPythonを十分に練習して読んでいないので、Pythonに精通していません。これをDFS図の子兄弟の概念に関連付けてコードを説明していただけますか？ありがとう。

4

3 に答える 3

4

それがDFSであることを確認するための鍵は、パスが蓄積される前に再帰が発生することです。言い換えると、再帰は「パス」リストに何かを入れる前に必要なだけ深くなります。最も深い兄弟はすべて、リストを返す前に「パス」に蓄積されます。

「paths」はすべてのパスのアキュムレータであるため、コードは「extend」ではなく「append」で正しいと思います。おそらく次のように書くことができますが

paths += find_all_paths(graph, node, end, path)

（編集）...代わりに

 newpaths = find_all_paths(graph, node, end, path)
 for newpath in newpaths:
     paths.append(newpath)
于 2010-11-20T03:03:52.943 に答える
4

次の変更と実行スクリプトを検討してください。

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    print 'adding %d'%start
    if start == end:
        return [path]
    if not graph.has_key(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            paths.extend(find_all_paths(graph, node, end, path))
    print 'returning ' + str(paths)
    return paths

G = {1:[2,3,4], 2:[1,4], 3:[1,4], 4:[1,2,3]}
find_all_paths(G, 1, 4)

出力：

adding 1
adding 2
adding 4
returning [[1, 2, 4]]
adding 3
adding 4
returning [[1, 3, 4]]
adding 4
returning [[1, 2, 4], [1, 3, 4], [1, 4]]

3を追加する前に最初のパスが返され、4を追加する前に2番目のパスが返されることに注意してください。

于 2010-11-20T03:21:55.630 に答える
1

はい、このアルゴリズムは確かにDFSです。基本的に実行可能なノード（たとえば、同じレベルの深さのすべて、別名兄弟）のリストを作成する幅優先探索とは対照的に、さまざまなノードをループするときに、それがどのようにすぐに繰り返されるか（子に入る）に注意してください。それらが要件に一致しない場合は繰り返します。

于 2010-11-20T02:59:42.193 に答える