为 DAG 分配优先级

Question

我将 DAG 存储为数组。如何以父节点获得最高优先级而所有叶节点获得最低优先级的方式为 DAG 分配优先级？

如果我有如下DAG

    A       # A -> B,C                      # A     
   / \      # B -> D        ----->          # B C   //can be used in parallel
  C   B     # C -> E                        # D 
  \    \    # D -> E                        # E
   \   D    # E ->                             
    \ /
     E

我将父项和子项都存储在我用作 DAG 的数组中。

拓扑排序 returns 线性列表，例如仅 A,C,B,D,E。

Answer 1

我认为您要找的东西叫做 topological ordering，一种对 DAG 中的节点进行排序的方法，这样在它的每个父节点之前就不会出现任何节点。幸运的是，可以使用各种拓扑排序算法非常有效地（在线性时间内）找到拓扑排序，包括基于 DAG 的简单 DFS 的算法。

希望对您有所帮助！

为 DAG 分配优先级

Assign priorities to DAG

java

directed-acyclic-graphs