图论算法查找出度为0和度为(n-1)的顶点 [英] Graph theory algorithm to find vertex with out-degree 0 and in-degree (n-1)

问题描述

我想知道如何确定有向图是否具有粘滞顶点，即定义为入度为n-1和出度为0的顶点.

I'm wondering how to determine whether a directed graph has a get-stuck vertex, which is defined as a vertex with in-degree n-1 and out-degree 0.

我认为愚蠢的方法是打印图形中每个顶点的入度和出度，但这是O(m + n).我对O(n)算法感兴趣.有什么想法吗?

I guess the dumb way would be to print the in-degree and out-degree of every vertex in the graph, but that's O(m+n). I'm interested in an O(n) algorithm. Any ideas?

谢谢！

推荐答案

我同意Beta，您无法通过o(n)解决此问题，因为您必须至少访问每个边缘一次以验证这是一个被卡住的节点.

I agree with Beta, there is no way you can solve this problem by o(n), because you have to visit each edge at least once to verify that it is a get-stuck node.

这篇关于图论算法查找出度为0和度为(n-1)的顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！