Python代碼列出依賴性，避免循環

-1

deps = { 
    'A': ['B', 'C', 'D'], 
    'B': ['C', 'E'], 
    'C': ['D', 'F'], 
    'D': ['C', 'G'], 
    'E': ['A'], 
    'H': ['N'], 
}

這意味着項目「A」取決於項目「B」，「C」，和'D'等。顯然，這可能是任意複雜的。

你怎麼寫一個函數get_all_deps(item)，讓您的item所有依賴的列表，沒有重複，沒有item。例如：

> get_all_deps('H') 
['N'] 
> get_all_deps('A') 
['B', 'C', 'D', 'E', 'F', 'G'] 
> get_all_deps('E') 
['A', 'B', 'C', 'D', 'F', 'G']

我正在尋找簡潔的代碼 - 理想情況下是一個遞歸函數。性能不是非常重要的，我的使用情況 - 我們正在談論的相當小的依賴關係圖（如幾十個項目）

來源

2017-01-09 Jordan Dimov

哦，像傳遞閉包的依賴？ – Tagc

你有沒有做過一個嘗試，或者你只是想要一個答案？ – depperm

歡迎來到StackOverflow。請閱讀並遵守幫助文檔中的發佈準則。 [在主題]（http://stackoverflow.com/help/on-topic）和[如何提問]（http://stackoverflow.com/help/how-to-ask）適用於此處。 StackOverflow不是一個編碼或教程服務。您已被給予廣度優先搜索的參考;請在實施過程中遇到問題時再次發帖。 – Prune

可以使用堆疊/待辦事項列表，以避免重複執行：

deps = { 
    'A': ['B', 'C', 'D'], 
    'B': ['C', 'E'], 
    'C': ['D', 'F'], 
    'D': ['C', 'G'], 
    'E': ['A'], 
    'H': ['N'], 
} 

def get_all_deps(item): 
    todo = set(deps[item]) 
    rval = set() 
    while todo: 
     subitem = todo.pop() 
     if subitem != item: # don't add start item to the list 
      rval.add(subitem) 
      to_add = set(deps.get(subitem,[])) 
      todo.update(to_add.difference(rval)) 
    return sorted(rval) 

print(get_all_deps('A')) 
print(get_all_deps('E')) 
print(get_all_deps('H'))

結果：

['B', 'C', 'D', 'E', 'F', 'G'] 
['A', 'B', 'C', 'D', 'F', 'G'] 
['N']

todo set包含要處理的元素。

彈出一個元素，並把它在返回值列表
循環播放，直到沒有更多的元素（還好有一個環在這裏）
只添加的元素，如果他們不是已經在返回處理值。
返回排序列表

的set差異避免了循環依賴的問題，避免了「最大遞歸深度」。只有限制是系統內存。

來源

2017-01-09 17:48:50

太好了，謝謝。我正在嘗試一個遞歸變體（例如傳遞一個'看到'設置遞歸），但沒有得到它的任何地方。堆棧技巧是偉大的。我仍然想知道是否有一種巧妙的遞歸方式。 –

Python代碼列出依賴性，避免循環

回答

相關問題