DAG - 确保存在单个源和单个接收器的算法

Question

我必须确保我们的应用程序中的图形是具有唯一源和独特接收器的DAG.

具体而言,我必须确保对于给定的起始节点和结束节点(两者都在一开始就知道),图中的每个节点都位于从起始节点到结束节点的路径上.

我已经有一个Tarjan算法的实现,我用它来识别周期,以及一个拓扑排序算法,我可以运行一旦Tarjan的算法报告图是一个DAG.

确保图表符合此标准的最有效方法是什么？

Answer 1

如果您的图由邻接矩阵表示，则如果矩阵的第 x 列为 0，则节点 x 为源节点；如果矩阵的行 x 为 0，则节点 x 为汇节点。您可以对矩阵运行两次快速传递以计算为 0 的行数和列数，以确定存在多少个源和汇以及它们是什么。这需要时间 O(n ² )，并且可能是检查这一点的最快方法。

如果你的图用邻接表表示，你可以通过检查是否有节点没有出边来在时间 O(n) 内找到所有汇节点。您可以通过为每个节点维护一个布尔值来找到所有接收器，该布尔值指示它是否有任何传入边（最初为 false）。然后，您可以在 O(n + m) 时间内迭代列表中的所有边，用传入边标记所有节点。未标记为具有传入边的节点就是源。这个过程需要时间 O(m + n) 并且开销很小，因此它可能是最快的方法之一。

希望这可以帮助！