高效的图遍历算法

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 添加到准备处理的顶点集中。