在有向无环图中检测汇点

Question

假设在一个DAG中存在一个具有以下属性的顶点：

1. 所有顶点都与它相连

2. 它没有与任何顶点相连

这通常被称为汇顶点。

能否在图中的顶点数为n的情况下，在O(n)时间内检测出此顶点？

- Rohan Monga

---

图中是否可以存在多于一条从顶点A到顶点B的边？ - Heatsink

不，一对顶点只有一条边。 - Rohan Monga

Answer 1

由于图中没有环，且所有顶点都与汇点相连，因此只需选择任意起始节点并随机行走。当您无法继续行走时，最多经过n步就能到达汇点。

一旦您走了n步（或更少且无法继续），由于问题不能保证存在汇点，您应该检查自己是否在汇点。这会增加另一个O(n)的时间复杂度。所以该问题的时间复杂度为O(2n)=O(n)。

- Dr. belisarius

---

不能保证存在唯一的汇点——有向无环图可能是不连通的。这种方法无法告诉您是否所有顶点都与找到的节点相连。 - Heatsink

如果断开连接，那么所有的顶点都不能与它相连，对吗？ - Loïc Février

@Heatsink，所以如果你走了n步，而且你还没有到达水槽，那么它就不存在（也就是没有循环）。 - Dr. belisarius

@Loïc Février 停止后，您可以在 O(n) 的时间内检查是否在汇聚处，因此问题仍然是 O(n)。请参见编辑。 - Dr. belisarius

@belisarius 如何在O(n)时间内检查它。我可以想到一个带有反向邻接列表的BFS。你有更好的解决方案吗？ - Loïc Février

Answer 2

我能想到的最好时间复杂度是 O(n + m)，如果 m 是 O(n)，那么它就是 O(n)。

假设有一个汇点存在，对图进行拓扑排序。排序中的最小节点就是汇点。请注意，拓扑排序的时间复杂度为 O(n + m)。

我之前在这里提供了一个实现，可以轻松修改以解决这个问题。

- jason

---

在这种情况下，如果图的表示是邻接表，则拓扑排序的时间复杂度为O(n+m)。 - Saeed Amiri

你可以更新你的答案: 为了检查它是否为汇点（此图中可能没有汇点），反转邻接表而不是进行DFS，并计算到达的节点数。 - Loïc Février

你需要先了解并学会如何实现“查找拓扑排序算法”。 - nbro

Answer 3

如果您可以在线性时间内计算节点的边数，那么这是可能的。首先，找到没有出边的顶点（扫描所有节点需要O(n)）。只有当恰好有一个这样的顶点时，您的条件才能得到满足。然后，计算它的入边（扫描所有输入边需要O(n)）。只有当恰好有n-1个入边时，您的条件才能得到满足。如果任一测试失败，则不存在汇点。

我假设“连接”是指“通过边连接”，而不是“通过路径可达”。

- Heatsink

---

不好：这是一个有向无环图，这个节点可能没有 n-1 个输入。想想 A->B->C。C 是汇点。 - Loïc Février

如果“全部连接”，那么为什么还需要DAG？这里的“连接”指的是路径。 - Loïc Février

@Loïc Février，认为a是一个星形节点，b->a，c->a，b->c是DAG，从b到a有两条路径，没有问题。 - Saeed Amiri

@Loïc 你可能是对的，Bronzebeard 更关心路径而不是边缘。 - Heatsink

@Loïc Février，不，你应该有b->c，因为这是一个问题陈述，它不是图中的真正汇点，而是特定于此问题的汇点。 - Saeed Amiri