設(shè)T 是一棵帶權(quán)樹(shù)，樹(shù)的每一條邊帶一個(gè)正權(quán)。又設(shè)S 是T 的頂點(diǎn)集,T/S 是從樹(shù)T 中
將S中頂點(diǎn)刪去后得到的森林。如果T/S中所有樹(shù)的從根到葉的路長(zhǎng)都不超過(guò)d ，則稱T/S
是一個(gè)d 森林。
(1)設(shè)計(jì)一個(gè)算法求T的最小頂點(diǎn)集S，使T/S是d 森林。(提示：從葉向根移動(dòng))
(2)分析算法的正確性和計(jì)算復(fù)雜性。
(3)設(shè)T中有n 個(gè)頂點(diǎn)，則算法的計(jì)算時(shí)間復(fù)雜性應(yīng)為O(n)。
標(biāo)簽：
樹(shù)
上傳時(shí)間：
2015-05-31
上傳用戶：我們的船長(zhǎng)
