6

假设我们有一个有一个源的 DAG。我想找到这样的节点n，使得来自源的任何完整路径都贯穿n（即n支配所有接收器）。换句话说：如果我们删除 的所有后继者n，那么所有路径都将以 结尾n。问题是节点在 DAG 中被增量标记为已删除。随着节点被标记为删除，其他节点可以开始满足上述属性。我怎样才能有效地检测到这种情况？

如果数据结构可以以比在每个源上单独运行单个源的算法更有效的方式对多个源执行此操作，则可以加分。

4

1 回答 1

3

对这个 DAG 进行拓扑排序，为其节点建立某种顺序。对于每个节点，其值将是所有先前节点的出边数减去所有先前节点和当前节点的入边数。“支配者”节点的值始终为零。

某个节点被标记为“删除”后，将其前任和后继节点放入优先队列。优先级由拓扑排序顺序决定。在“已删除”节点之后更新所有节点的值（添加传入节点的数量并减去该节点的传出节点数量）。同时（以相同的顺序）递减优先级队列中的前任节点和“删除”节点之间的每个节点的值，并从优先级队列中的后继节点开始递增每个节点的值。当某个节点的值减为零时停止。这是一个新的“支配者”节点。如果需要所有“支配”节点，请继续直到图表结束。

delete(delNode):
  for each predecessor in delNode.predecessors: queue.add(predecessor)
  for each successor in delNode.successors: queue.add(successor)
  for each node in DAG:
    if queue.top.priority == node.priority > delNode.priority:
      ++accumulator

    node.value += accumulator
    if node.value == 0: dominatorDetected(node)

    if node.priority == delNode.priority:
      accumulator += (delNode.predecessors.size - delNode.successors.size)
      node.value = -1

    if queue.top.priority == node.priority:
      queue.pop()
      if node.priority < delNode.priority:
        --accumulator

    if queue.empty: stop

对于多源情况，可以使用相同的算法，但为每个节点保留一个“值”列表，每个源一个值。算法复杂度是O(Nodes * Sources)，与对每个源的独立搜索相同。但是如果使用矢量化，程序可能会更高效。“值”可以与 SIMD 指令并行处理。现代编译器可能会进行自动矢量化来实现这一点。

于 2012-02-06T16:08:50.660 回答