d森林问题java算法实验报告

设T 是一棵带权树,树的每一条边带一个正权。又设S 是T 的顶点集,T/S 是从树T 中将S中顶点删去后得到的森林。如果T/S中所有树的从根到叶的路长都不超过d ,则称T/S是一个d 森林。 (1)设计一个算法求T的最小顶点集S,使T/S是d 森林。(提示:从叶向根移动) (2)分析算法的正确性和计算复杂性。 (3)设T中有n 个顶点,则算法的计算时间复杂性应为O(n)。