有效计算动态有向无环图上可达权和的数据结构

Question

我有一个有向无环图，其中每个顶点都有一个"重量；属性从初始顶点可到达的顶点是从初始顶点开始沿一条或多条边可到达的所有顶点的集合。可达权重和是从初始顶点到可达顶点的所有权重的和。此外，我可以随意向图中添加有向边和顶点，但图将始终保持非循环。

有没有任何数据结构我可以用它来扩充图，这将有助于从任何给定的初始顶点有效地计算可达权重和，并且在更新图时可以更新？

Answer 1

如果添加一个节点，该节点具有从初始节点到可达节点的链接，则可达权重将按新节点的权重递增。否则，如果新节点未链接到任何可达节点，则可达权重不受影响。

因此，如果您有一个从未更改的初始节点，那么存储其所有可到达节点的集合是值得的。然而，如果你想优化任何节点的可达权重的更新，那么存储每个节点的可达节点是不值得的——重复使用的存储量将大于图。