Roh*_*nga 5 algorithm graph sink-vertex
假设在一个顶点中有一个具有以下属性的顶点DAG:
所有顶点都连接到它
它没有连接到任何顶点
这通常称为接收器顶点.
是否有可能检测到这个顶点O(n),n图中的顶点数量在哪里？
由于图中没有循环,并且所有顶点都与接收器连接,只需选择任何起始节点并开始随机行走.当你无法继续行走时,你就在最近的n个台阶上.
一旦你走了n步(或更少,你不能继续),因为问题并不能保证有一个水槽,你应该检查你是否在一个.这增加了另一个O(n).所以问题是O(2 n) = O(n)