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

Question

所以我正在构建一个 Web 应用程序，您可以在其中构建一个有向图，其中一个节点将代表一些操作，而边缘将代表这些操作之间的数据流。所以对于边 {u,v} ， u 必须在 v 之前运行。单击此链接以查看示例图

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

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

Answer 1

这是拓扑排序的一个完美例子。最常见的通过遍历创建集合的算法是Kahn 算法。伪代码如下所示，维基百科链接中的信息应该足以让您入门。

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启动的节点。如果您想了解其他信息，请在评论中告诉我。