按顺序访问 DAG 节点的最有效方法

Question

我有一个大型（100,000+ 个节点）有向无环图（DAG），并且希望按顺序在每个节点上运行“访问者”类型函数，其中顺序由图中的箭头定义。即保证在节点本身之前访问节点的所有父节点。

如果两个节点不直接或间接互相引用，那么我不在乎它们被访问的顺序。

最有效的算法是什么？

Answer 1

您必须对节点执行拓扑排序，并按结果顺序访问节点。

此类算法的复杂度为O(|V| + |E|)。可以说，这也是您想要执行的操作的下限，因为您 a) 想要访问所有节点，b) 不能真正忽略任何边，因为即使是单个边也会显着影响排序。

Answer 2

这里有一些答案： 良好的图遍历算法

这里： http://en.wikipedia.org/wiki/Topological_sorting

一般来说，访问一个节点后，应该访问它的相关节点，但只能访问尚未访问过的节点。为了跟踪已访问的节点，您需要将节点的 ID 保留在集合（或映射）中，或者您可以将节点标记为已访问（以某种方式）。

如果你关心拓扑顺序，你必须首先获取一个节点的所有未遍历链接（“剩余链接”）的集合，按引用节点的 id 排序（通常：map(node-ID -> 链接计数））。如果您还没有，您可能需要使用类似于上述方法的方法来构建它。然后，首先访问剩余传入链接计数为零的节点。对于来自该节点的每个链接，减少每个相关节点的剩余链接计数，如果计数达到零，则将相关节点添加到要访问的节点集（或仅访问该节点）。

Answer 3

正如其他答案中提到的，这个问题可以通过拓扑排序来解决。

一个非常简单的算法（不是最有效的）：

Keep an array (or map) indegree[] where indegree[node]=number of incoming edges of node

while there is at least one node n with indegree[n]=0:
   for each node n in nodes where indegree[n]>0:
      visit(n)
      indegree[n]=-1 # mark n as visited
      for each node x adjacent to n:
          indegree[x]=indegree[x]-1 # its parent has been visited, so one less edge coming into it

Answer 4

您可以通过从入度为零的每个节点运行 dfs 来以 O(N) 遍历 DAG（无需任何顶排序），因为这些将是有效的“起点”。这是可行的，因为图没有循环，那些零入度节点必须存在，并且必须遍历整个图。