그래프에서 가장 큰 가족 찾기

Question

이것은 데이터 구조 과정의 숙제입니다. 코드를 묻지는 않지만 다음과 같은 효과적인 알고리즘을 찾기가 힘듭니다. l

다른 패밀리 트리에 대한 정보가 있습니다. 그 중에서 가장 큰 가족을 찾아서 가장 큰 장로의 이름과 그의 후손의 이름을 돌려 주어야합니다. 자손은 그들 사이에 아이를 가질 수 있습니다 (형제와 자매는 아이를 가질 수 있습니다). 그리고 이것은 최소한 O (n^2)에서 이루어져야합니다.

이 문제를 해결하는 가장 효과적인 방법은 무엇입니까? 그래프에 대한 폭 넓은 첫 번째 검색을한다고 상상해 봅니다.하지만 이는 많은 레벨의 어린이 카운터를 계속 유지해야한다는 것을 의미합니다 (예를 들어 99 명의 어린이를 횡단하는 경우).

Answer 1

CMIIW하지만 모든 가계도는 서로 분리되어 있으며 루트는 가장 오래된 조상입니다. 그렇다면 모든 트리 노드를 수에 관계없이 계산하기 때문에 모든 가중치가없는 그래프 탐색 알고리즘이 동일한 결과를 제공한다고 생각합니다. BFS가 그 일을 할 것입니다. 나는 당신이 "많은 단계를 위해 아이들 카운터를"위쪽으로 유지하는 것을 의미하는 것을 얻지 못한다. 그러나 단지 1 명의 카운터가 괜찮은가?