圖遍歷確保父母先被訪問

我想創建一個工作流管理，我代表工作流我的圖。該圖是一個簡單的有向圖，其中節點表示一些任務，並且邊指向依賴於具有父 - >子關係的任務的任務。現在，我想要實現的是，只有在所有父母都完成之後，才能開始任務。圖遍歷確保父母先被訪問

所以說我有表示爲Python字典下面的圖：

graph = {'A': ['B', 'D'], 'B': ['D', 'C'], 'C': ['D', 'E'], 
    'D': ['E'], 'E': []}

在這種情況下，A應該執行第一後跟B其然後隨後C。之後D得到執行，最後完成的任務E取決於D。

我可以設想的一種方式是使用寬度或深度優先搜索來訪問所有節點，然後檢查每個節點是否所有父母都已完成。如果是的話，我開始這個任務，我一直這樣做直到所有任務都開始。

我想知道是否有更復雜/有效的解決方案來解決這個問題，而不是多次遍歷圖形？

來源

2016-08-02 Luca

我想你提到的問題是，[拓撲排序（https：//開頭恩.wikipedia.org /維基/ Topological_sorting）。 – arekolek

[我如何訂購連接列表]可能的重複（http://stackoverflow.com/questions/16409486/how-can-i-order-a-list-of-connections） – arekolek

它是圖遍歷還是樹穿越？ 'C_3'的預期輸出是什麼？ – xenteros

這取決於你的圖形數據結構。

如果圖形存儲爲節點，則可以使用BFS，因爲您將從同級別的依賴關係的任務轉移到葉子（最小任務依賴性）到同一級別的任務（最小任務依賴性）。

如果您的圖形按照您的說明存儲爲鄰接列表，您應該進行拓撲排序，從最大任務依賴性逐步獲取最小任務依賴性。

這會給你然後 O（n）遍歷圖的複雜度。

來源

2016-08-02 12:18:47 hmicn

你不需要多次遍歷。只需一個簡單的BFS就可以完成這項工作。在BFS中，父母總是在孩子面前拜訪。

來源

2016-08-02 12:00:05 Pranalee

您可以使用圖書館像graph_tool已經topological sort實施：

graph = {'A': ['B', 'D'], 'B': ['D', 'C'], 'C': ['D', 'E'], 'D': ['E'], 'E': []} 
i2a = dict(enumerate(graph)) 
a2i = {v:k for k,v in i2a.items()} 

import graph_tool.all as gt 
g = gt.Graph() 
g.add_edge_list([(a2i[s], a2i[t]) for s in graph for t in graph[s]]) 
print(*[i2a[v] for v in gt.topological_sort(g)])

輸出：

A B C D E

來源

2016-08-02 12:52:36 arekolek

感謝您的提示。我可以使用外部庫的某些約束，但知道這一點非常有用！ – Luca

圖遍歷確保父母先被訪問

回答

相關問題