algorithm - 图 : find a sink in less than O(|V|) - or show it can't be done

Question

我有一个图，其中 n 个节点作为邻接矩阵。

是否有可能在 O(n) 时间内检测到接收器？

如果是，怎么办？如果不是，我们如何证明？

汇点是一个有来自其他节点的入边但没有出边的顶点。

Answer 1

阅读 SPWorley 提供的链接时，我想起了用于查找数字数组中最小元素的锦标赛树算法。树顶部的节点是最小元素。由于链接中的算法还谈到了两个节点 (v,w) 之间的竞争，如果 v->w 则由 w 接替，否则由 v 接替。我们可以使用类似于寻找最小元素的算法来找出汇点。但是，无论汇是否存在，都会返回一个节点。但是，如果存在接收器，它总是会被返回。因此，我们最终必须检查返回的节点是否为接收器。

//pseudo code
//M -> adjacency matrix
int a=0
for(int i=1;i<vertices;++i)
{
  if(M[a,i]) a=i;
}

//check that a is sink by reading out 2V entries from the matrix
return a; //if a is a sink, otherwise -1