在表中表示图形，并给定访问的节点接下来要访问的节点

Question

>假设我有一个包含 N 个节点 111,222,...,nnn 的图形，例如，我有下表中表示的图形

NodeID  |   PredecessorID
222         111
333         111
555         222
555         333

等等。

给定已访问的 M 个节点的列表，如何找到接下来要访问的所有节点？接下来要访问的节点是其所有前置任务都已访问的节点。

Answer 1

如果你的列表 M 包含所有访问过的节点，而不仅仅是其中的一个子集，你可以这样做：

foreach n in N:
    visite = True
    if n is not marked:
        foreach predecessor (pn) of n:
            visite = visite and (is pn marked)
    if visite = True:
        add n to visitable nodes

在最坏的情况下，predecessors of n的数量是N（完整的图），所以它的运行时复杂度是O（N^2）