조상 찾기 알고리즘

Question

시험에서 질문했습니다. 해결책을 찾을 수 있도록 도와 주시겠습니까?

것은 설계 알고리즘을 사용하여 (a 트리 또는 그래프)는 주어진 노드의 조상의 번호를 찾는 :

1. O (m) 메모리
2. 무제한 메모리 크기

Answer 1

알고리즘은 트리의 디자인에 의존합니다. 그것은 합리적인 구현에 문제를 제기하지 않는

int ancestors = 0; 
while(node = node->parent) ancestors++; 

제약에 감소하는 경우에 가장 간단한 예는 부모를 포함하는 노드입니다.

노드에이 없으면 트리의 구조에 따라 다릅니다. 정렬되지 않은 트리의 가장 복잡한 경우

• 그것은 조상을 계산, 전체 트리 검색을 수반한다.
• 검색 트리의 경우 검색 만하면됩니다.

Answer 2

DFS 루프는 노드 k의 조상을 계산하는 데 사용할 수 있습니다. 각 반복에서 카운트 된 노드와 노드를 두 번 방문한 donot 수를 표시하면됩니다.

for i in graph visited[i] = false // for DFS 

for i in graph counted[i] = false // for ancestors 

int globalcount = 0; // count the no of ancestors 

for i in graph DFS(i,k) //DFS-loop 

def bool DFS(u,k) { //K is the node whos ancestors want to find 


if(!visited[u]) { 

visited[u] = true // prevent re-entering 

totalret = false // whether there is path from u to k 

for each edge(u,v) { 

retval = DFS(v) 

if(retval&&!counted[u]&&u!=k) { //there is path from u to k & u is not counted 

    globalcount++ 

    counted[u] = true 

    totalret = true 

} 

} 

if(u == k) return true 

else return totalret 

} 

return counted[u] // if visited already and whether ancestor(k)? 
} 

print globalcount // total ancestor(k) 

공간의 복잡성 : O(V) V : 정점

시간 복잡도의 번호 : O(E) E : 그래프의 가장자리에는 전체 그래프에