向无环图的遍历在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中唯一启动的节点。如果您想获得其他信息，请在评论中告诉我。