在python中編寫更好的遞歸深度優先搜索

我試圖在python中（與標準圖算法一起）構建圖庫。我試圖實現DFS，這是它看起來像在python中編寫更好的遞歸深度優先搜索

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使用，我無法想出，工程實施像上面一樣。有人能給我一些關於我如何實現這一目標的指針嗎？

來源

2012-12-04 Prakhar

只是讓調用你已經有一個包裝方法：

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

這裏DFS2是你在上面顯示的方法。

來源

2012-12-04 09:53:02

非常愚蠢的我沒有想到這一點！非常感謝 – Prakhar

@Prakhar：好好學習，因爲你可能會遇到很多次需要。這是計算機科學發揮基本規律的一個例子，它說所有問題都可以通過另一個層面的間接方式來解決。 – martineau

其實你爲什麼不設置path就有一個空列表的默認值？因此，使用你的代碼，但略有不同的論點：

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

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

# From here you can do 
DFS(gr, s)

來源

2014-03-04 19:06:29 chutsu

我肯定不會推薦這個解決方案。傳遞可變對象作爲默認參數可能會導致意外行爲。查看[Mutable Default Arguments]（http://python-guide-pt-br.readthedocs.io/en/latest/writing/gotchas/）。所以最好傳遞None作爲路徑的默認值，如果path爲None，則創建一個新的空路徑列表。 – 2006pmach

在python中編寫更好的遞歸深度優先搜索

回答

相關問題