什麼是這種類型的圖形，我可以用什麼算法來遍歷它？

Question

我有一個「節點」的網絡，每個節點產生「結果」。每個節點和結果都有一個唯一的名稱/ ID。結果用作每個節點的輸入和輸出。當所有輸入結果都可用於節點時，它可以被執行。節點完成執行其輸出結果時將可用。

因此，例如：

input node output 
     A x 
x  B y,z 
x,z C q 

在上述網絡。節點A沒有輸入，可以先執行。然後當結果x變爲可用時，B可以被執行。當A和B都完成時，C可以被執行，因爲它取決於A和B的結果。結果也可以是最終產品，例如y，在這種情況下，它不被用作任何節點的輸入。

網絡可能要複雜得多。每個節點都可以產生多個結果，並且可以有多個輸入依賴關係。

我希望能夠選擇一個結果，說「q」，並找出需要執行哪些節點才能到達那裏。我想在一個更大的節點網絡中做到這一點。

我覺得這是一種常見的算法，但我沒有這方面的經驗。它不像層級樹那樣分層，因爲依賴可以創建圓圈。從我讀過的內容來看，我認爲它必須是一種森林圖。

無論如何它必須是可穿越的。總是至少有一個節點可以首先執行，其他所有節點都應該能夠按照某種順序執行，而不會造成2個節點正在等待彼此完成的死鎖。

在代碼中描述這個網絡/它的節點的常用方法是什麼？這種網絡的官方名稱是什麼？

Answer 1

您正在查找的名稱是'依賴關係圖'。

用來分解算法被稱爲「拓撲排序」（見：http://en.wikipedia.org/wiki/Topological_sorting）

其中最有名的工具解決這些依賴關係被稱爲使。

對應你的例子會是這個樣子的Makefile文件：

x : 
    echo node A 

y z : x 
    echo node B 

q : x z 
    echo node C 

正如你所看到的語法幾乎是相同的例子使用的表之一。唯一的主要區別是，「列」的順序是顛倒的 - 說「要......我首先需要......」而不是「從......我可以去......」。

鍵入make <TARGET>您可以輕鬆驗證它是否按照您希望的順序解析了節點。這裏是一些例子：

make q 
    * node A 
    * node B 
    * node C 

make x 
    * node A 

make z 
    * node A 
    * node B 

（爲了使輸出一點點漂亮這是用於上述的輸出的版本：

x : 
    @echo " * node A" 

y z : x 
    @echo " * node B" 

q : x z 
    @echo " * node C" 

）從只是作爲一個類型的圖

Answer 2

除了，這聽起來像你想要的語義是類似於帶有彩色令牌的Petri net。 Petri網的可達性分析是文獻中存在算法的一個已經確立的問題。也許維基百科的文章會給你一些啓發的想法。