4

私はPythonでグラフライブラリを構築しようとしています（標準のグラフアルゴリズムと一緒に）。DFSを実装しようとしましたが、これは次のようになります。

def DFS(gr, s, path):
    """ Depth first search 
    Returns a list of nodes "findable" from s """
    if s in path: return False
    path.append(s)
    for each in gr.neighbors(s):
        if each not in path:
            DFS(gr, each, path)

これは正常に機能していますが、使用方法に満足していません。たとえば、現在これを行う必要があります

 path = []
 DFS(mygraph, "s", path)
 print path

これの代わりに、DFSをこのように使用したい

path = DFS(mygraph, "s")
print path

再帰的なDFSでは、上記のように機能する実装を思い付くことができません。誰かが私にこれをどのように達成することができるかについてのいくつかの指針を与えることができますか？

4

3 に答える 3

4

すでに持っているものを呼び出すラッパーメソッドを作成するだけです。

def DFS(gr, s):
    path = []
    DFS2(gr, s, path)
    return path

これがあなたDFS2が上で示した方法です。

于 2012-12-04T09:53:02.613 に答える
3

path実際、デフォルトの空のリストを設定しないのはなぜですか？したがって、同じコードを使用しますが、引数は少し異なります。

# Original
def DFS(gr, s, path):

# Modified
def DFS(gr, s, path=[]):

# From here you can do
DFS(gr, s)
于 2014-03-04T19:06:29.167 に答える
2

chutsuが提案するように、訪問先ノードには空のデフォルト値を使用できますが、可変のデフォルト引数の使用には注意してください。また、一定のルックアップにはリストの代わりにセットを使用することをお勧めします。

def DFS(gr, s, visited=None):
    """ Depth first search 
    Returns a list of nodes "findable" from s """
    if visited == None:
        visited = set([s])

    for each in gr.neighbors(s):
        if each not in visited:
            visited.add(each)
            DFS(gr, each, visited)

    return visited
于 2018-10-01T07:41:43.803 に答える