这是数据结构课程的作业 . 我不是要求代码，但我很难为此提出一个有效的算法：l
我有关于不同家谱的信息 . 在那些我必须找到最大的家庭，并返回最伟大的老人的名字和他的后代的数量 . 后代可能在他们之间有孩子（兄弟和姐妹可能有孩子），这必须至少在O（n ^ 2）完成 .
解决这个问题的最有效方法是什么？我想在图表上进行广泛的第一次搜索，但这意味着我必须将儿童计数器保持在很多级别以上（例如，如果我正在遍历一个盛大的^ 99个孩子） .
CMIIW，但我的假设是每个家族树彼此分开，根是最老的祖先 . 如果是这种情况，因为你无论如何计算所有树节点，我认为任何未加权的图遍历算法都会给出相同的结果 . BFS会做这个工作 . 我不明白你的意思是“把儿童柜台保持在很多级别以上”但是，只有1个柜台很好吗？
1 回答
CMIIW，但我的假设是每个家族树彼此分开，根是最老的祖先 . 如果是这种情况，因为你无论如何计算所有树节点，我认为任何未加权的图遍历算法都会给出相同的结果 . BFS会做这个工作 . 我不明白你的意思是“把儿童柜台保持在很多级别以上”但是，只有1个柜台很好吗？