如何在O(V)中只有邻接矩阵的简单DAG中求出度等于v-1的顶点？
如何在O(V)中只有邻接矩阵的简单DAG中求出度等于v-1的顶点？
提问于 2020-10-31 17:55:39
我有一个简单有向图，没有反平行边.我需要找到一种算法来确定这个图是否包含一个顶点，其中out-deg=区V_x=-1和in-deg=0。
该算法的输入只能是该图的adjacency-matrix。利用这个邻接矩阵，我们需要在O( And )中这样做。
谢谢你的帮助。
回答 1
Stack Overflow用户
发布于 2020-10-31 18:06:37
因为最多只能有一个这样的节点，所以可以通过迭代地消除候选节点来完成这一任务。
首先，将所有节点放到堆栈上。我们将使用这个堆栈来保留我们的候选人。
只要堆栈上至少有两个节点p和q，就检查边缘(p, q)是否存在。如果它存在，那么q就不能有0度，我们可以将它从堆栈中删除.如果它不存在，那么p就不能有出度|V|-1，所以我们可以将它从堆栈中删除。因此，在每次检查之后，我们会准确地删除一个候选，这允许我们在O(|V|)检查之后到达单个候选。
现在，我们只需要通过检查邻接矩阵中相应的行和列来检查这个节点是否为给定的入、出度，这也可以在O(|V|)中完成。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/64624835
复制相关文章
相似问题
腾讯云开发者
