0

这是数据结构课程的作业。我不是要代码，但我很难为此想出一个有效的算法：l

我有关于不同家谱的信息。其中，我要找出最大的家族，并返回最大的长老的名字和他的后代人数。后代之间可能有孩子（兄弟姐妹可能有孩子），这必须至少在 O(n^2) 内完成。

解决这个问题的最有效方法是什么？我想在图表上进行广度优先搜索，但这意味着我必须向上保持多个级别的儿童计数器（例如，如果我正在遍历一个盛大的 ^ 99 个儿童）。

4

1 回答 1

0

CMIIW，但我的假设是每个家谱都是相互分离的，根是最古老的祖先。如果是这种情况，由于您无论如何都要计算所有树节点，我认为任何未加权图遍历算法都会给出相同的结果。BFS 会完成这项工作。不过，我不明白您所说的“将儿童计数器向上保持多个级别”是什么意思，只有 1 个计数器就可以了，对吧？

于 2014-11-16T12:32:59.747 回答