假设 DAG 中有一个顶点具有以下属性:
所有顶点都连接到它
它不连接到任何顶点
这通常称为汇点。
是否有可能在 O(n) 中检测到这个顶点，其中 n 是图中的顶点数？
最佳答案
由于图中没有环，所有顶点都与汇点相连，只需选择任何起始节点并开始随机行走。当你无法继续行走时，你就在水槽边，最多走 n 步。
一旦你走了 n 步(或更少，你就不能继续)，因为这个问题不能保证有一个汇，你应该检查你是否在一个。这增加了另一个 O(n)。所以问题是O(2 n) = O(n)
关于algorithm - 检测有向无环图中的汇点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4137481/