高效图遍历算法

Question

我正在为以下用例搜索算法或算法的想法：

有向图由多个顶点组成。其中一些顶点用值（如数字）注释，并且没有父顶点（前任）。所有其他顶点都代表操作。仅当父顶点（前驱顶点）的所有注释值都已知时，才能执行操作。然后将操作的结果或值存储在顶点中。

我的解决思路：

1. 将至少有一个父顶点（前任）的所有顶点存储在一个集合中
2. 虽然集合不为空：
   1. 从集合中获取下一个顶点
   2. 检查所有父顶点（前任顶点）的值是否已知
   3. 如果所有值都已知：
      1. 从集合中移除顶点
      2. 执行操作
      3. 将运算结果存入顶点
      4. 循环（转到 2。）
   4. 否则：循环（转到 2。）

我的问题：我认为这个解决方案思路可行，但效率不高（尤其是对于大型图结构）。

是否有更有效的方法来解决这个问题？

Answer 1

有一些可能性可以避免漫无目的地重新检查顶点，例如：

1. 初始化一个整数数组，存储每个顶点的父节点数。
2. 初始化一组有 0 个父节点的顶点（可以与步骤 1 同时完成）。
3. 直到该集合为空：
   1. 从该集合中取出一些顶点 a 并对其进行处理。
   2. 对于从 a 到顶点 b 的每条边，减少顶点 b 的父节点数。如果计数达到 0，将 b 添加到准备处理的顶点集。

Answer 2

想要做的事情叫做'topological sort'——按照你处理顶点的顺序，每个节点的前任必须在它做之前出现：https://en.wikipedia.org/wiki/Topological_sorting

有几种有效的算法。一个与您的非常接近，但是您只在没有未完成的前辈时才将顶点放入集合中。 （哈罗德的回答）

Answer 3

这本质上不就是一种层序遍历的问题吗？

鉴于此，

An operation can be only performed if all annotated values of the parent vertices (predecessors) are known.

您应该从没有父顶点的顶点开始。 （这部分你已经想好了。）

接下来，将它们放入一个队列中，而不是将它们放入一个集合中，这样先进先出的基础实际上允许您处理关卡中的每个顶点-明智的顺序。

如果无法计算出当前顶点的值，则将其放回队列中，否则将当前顶点可达的顶点放入队列中。保持具有可用所需父顶点值的顶点的计算值。

我几乎可以说，通过一些优化，这将是最有效的方法。