有效计算动态有向无环图上可达权和的数据结构
我有一个有向无环图，其中每个顶点都有一个“权重”属性。初始顶点的可达顶点是从初始顶点开始跟随一条或多条边可达的所有顶点的集合。可达权重和是初始顶点可达顶点上所有权重的总和。此外，我可以随意向图中添加有向边和顶点，但图将始终保持无环。
我是否可以使用任何数据结构来扩充图，这些数据结构将有助于从任何给定的初始顶点有效计算可达权重和，并且在图更新时可更新？
共有1个答案
如果添加了一个节点，该节点具有从初始节点到可到达节点的链接，则可到达权重将按新节点的权重递增。否则，如果新节点未链接到任何可到达节点，则可到达权重不受影响。
因此，如果您有一个从不更改的初始节点，那么存储一组其所有可达节点是值得的。但是，如果您想优化来自任何节点的可达权重的更新，那么存储每个节点的可达节点是不值得的——存储结果将大于图。
-
因此，在Hackerrank上的一个名为“非循环图”的编程竞赛中出现了这个挑战，它基本上可以归结为计算“有向非循环图”中每个节点可达的节点数。例如，假设你有一个这样的图: 可达性计数（包括源节点）： 我的方法是“深度优先”遍历和记忆。环顾四周，但似乎运行时间无法进一步提高，因为在以下情况下会出现过度计数： 第三个节点将计算第四个节点，即使第二个节点已经计算了第四个节点。更糟糕的是，我只用JavaS
-
输入： 生成的树： 输出： 规则： < li >输入代码总是会产生一个有向无环图 < li >每个节点都有一些wait_time值 < li >完整的图形遍历应该计算整个图形的总等待时间 < li >必须并行遍历所有独立节点(或者至少时间计算应该是这样) < li >如果两个不同节点的wait_time发生重叠，则将考虑最大值，遍历时间较短的节点将移动到下一个独立节点 < li >除了根和叶(可以
-
给定一个有向无环图(DAG)，是否有一种算法在线性时间内运行，计算每个顶点（和该边的源）的同度，假设我们知道一个根节点（一个可以从它到达每个其他顶点的节点）？
-
我有一个有圈的有向图。所有边都是加权的，权重可以是负值。可能会有负循环。
-
我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望从你们那里得到一些反馈。谢谢 我的想法：对于每个叶节点，找到从根节点到它的最长路径。对于所有路径，找到最大路径长度 然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？ 我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关