Java Web 应用程序中的有向无环图遍历

Question

所以我正在构建一个 Web 应用程序，您可以在其中构建一个有向图，其中一个节点将代表一些操作，而边将代表这些操作之间的数据流。因此对于边 {u,v} ， u 必须在 v 之前 运行 。 Click this link to see a sample graph

START节点表示初始值，除输出外的其他节点按指定操作。输出节点将输出它作为输入接收的值。

我应该使用哪种算法方法来处理这样的图形？

Answer 1

这是拓扑排序的一个完美例子。通过遍历按照顺序要求创建集合的最常见算法是 Kahn's Algorithm。伪代码可以在下面看到，维基百科中的信息 link 应该足以让你入门。

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)

请注意 "starting node" 将通过在图中正确表示传入边来强制执行。它将是 S 中唯一开始的节点。如果您需要任何其他信息，请在评论中告诉我。