알고리즘 설계와 관련된이 흥미로운 질문을 발견했습니다. 제대로 풀 수 없었습니다.알고리즘 설계, 유향 그래프 알고리즘 구현
adjancency 목록을 사용하는 유향 그래프 G = (V, E) 및 정수 K < 감안 | V |가 선형 시간 복잡도의 알고리즘을 구현할 (O (N)), 만약 확인 그래프 G는 동일한 실수를 갖는 적어도 k 개의 꼭지점을 갖는다.
n == | V | + | E |
모든 에지를 통과하거나 심지어 노드의 모든 에지를 통과하는 것만으로도 가능하고 가능한 모든 정수에 대해 정점 수를 유지하는 것으로 충분합니다.
스케치 pyhon 스타일 방법을 :
def check(graph, k):
# For each vertex count indegree
indegrees = [0] * graph.number_of_nodes()
# 'Maps' number of vertices to indegree
num_with_indegree = [graph.number_of_nodes()] + [0] * (graph.number_of_nodes()-2)
# Pass through all edge innodes.
# This iteration is easy to implement with adjancency list graph implementation.
for in_node in graph.in_nodes():
# Increase indegree for a node
indegrees[in_node] += 1
# 'Move' vertex to it's indegree bucket
indegree = indegrees[in_node]
num_with_indegree[indegree-1] -= 1
num_with_indegree[indegree] += 1
# Returns true if any bucket has at least k vertices
return any(n >= k for n in num_with_indegree)
그것은'indegree' 있어야 undegree''가정하는 것이 안전합니까? 나는'undegree '에 대해 들어 본 적이 없다. – Paulpro
예, 고쳐 주셔서 감사합니다. 나는 지금 바로 잡는다. 보시다시피 영어는 제 모국어가 아닙니다. –
영어가 제게 좋을 것 같습니다. 그 단어에 대해서만 나는 확신이 없었습니다. 아마도 오타 일 것입니다. – Paulpro