Нахождение самой большой семьи в графе

Question

Это домашняя работа для курса по структурам данных. Я не прошу код, но мне трудно придумать эффективный алгоритм для этого:l

У меня есть информация о разных родословных. Среди них мне нужно выяснить самую большую семью и вернуть имя величайшего старца и количество его потомков. Потомки могут иметь детей между собой (у брата и сестры может быть ребенок), и это должно быть сделано как минимум за O(n^2).

Что было бы наиболее эффективным способом решить эту проблему? Я предполагаю, что сначала у меня будет широкий поиск по графикам, но это означает, что я должен поддерживать счетчики детей на много уровней вверх (если я, например, пересекаю великих 99 детей).

Answer 1

CMIIW, но я предполагаю, что каждое генеалогическое древо отделено друг от друга, и корень является старшим предком. Если это так, так как вы считаете все узлы дерева независимо, я думаю, что любой алгоритм обхода невзвешенного графа даст тот же результат. BFS сделает эту работу. Я не понимаю, что вы имеете в виду под "держать счетчики детей на много уровней выше", хотя, просто 1 счетчик подойдет, верно?