algorithm - 在有向无环图中检测汇

Question

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

1. 所有顶点都连接到它

2. 它没有连接到任何顶点

这通常称为汇顶点。

是否可以在图中检测到这个顶点O(n)，n图中的顶点数在哪里？

Answer 1

由于图中没有环，且所有顶点都与 sink 相连，因此只需选择任意起始节点并开始随机行走。当你不能继续走路时，你就在水槽边，最多走 n 步。

一旦你走了 n 步（或更少并且你不能继续），由于问题不能保证有一个水槽，你应该检查你是否在一个。这又增加了一个O(n). 所以问题是O(2 n) = O(n)

Answer 2

我能想到的最好的O(n + m)就是O(n)if mis O(n)。

假设存在汇，对图进行拓扑排序。排序中的最小节点是一个接收器。注意拓扑排序是O(n + m).

我之前在这里提供了一个实现，可以很容易地针对这个问题进行修改。

Answer 3

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

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