向無環圖的遍歷在Java Web應用程序

Question

所以我建立一個Web應用程序，你可以建立一個向圖，其中一個節點將代表的一些操作和邊緣將代表這些操作之間的數據流。所以對於邊緣{u，v}，你必須在v之前運行。 Click this link to see a sample graph

START節點表示初始值和作爲指定的除輸出的其他節點確實操作。輸出節點將輸出它接收的值作爲輸入。

我應該使用哪種算法的方法來處理這樣的圖形？

Answer 1

這是一個拓撲排序的一個很好的例子。通過遍歷遵循訂單要求創建集合的最常見算法是Kahn's Algorithm。僞代碼可以在下面看到，維基百科鏈接中的信息應該足以讓你開始。

L ← Empty list that will contain the sorted elements 
S ← Set of all nodes with no incoming edges 
while S is non-empty do 
    remove a node n from S 
    add n to tail of L 
    for each node m with an edge e from n to m do 
     remove edge e from the graph 
     if m has no other incoming edges then 
      insert m into S 
if graph has edges then 
    return error (graph has at least one cycle) 
else 
    return L (a topologically sorted order) 

請注意，「起始節點」將通過適當地表示圖形中的傳入邊緣來執行。它將成爲S中唯一啓動的節點。如果您想獲得其他信息，請在評論中告訴我。