标签列表
首页
标签
sink-vertex
关联标签
algorithm
graph
computer-science
graph-theory
按时间
按得票
10
得票
7
回答
图论:在不超过O(|V|)的时间内找到汇点 - 或者证明无法完成
我有一个包含n个节点的邻接矩阵图。 是否可能在少于O(n)时间内检测出汇点(sink)? 如果可以,该如何检测?如果不行,如何证明? 汇点顶点是一条入边均来自其他节点而没有出边的顶点。
algorithm
graph
computer-science
graph-theory
sink-vertex