1
給定具有N個節點的連通的無向非循環圖,如何在線性時間內找到跨越圖中所有節點的每棵樹的高度?連接的無向非循環圖中所有可能樹的高度
給定具有N個節點的連通的無向非循環圖,如何在線性時間內找到跨越圖中所有節點的每棵樹的高度?連接的無向非循環圖中所有可能樹的高度
改寫:給出的無根樹T,計算,爲T,根樹T(V)由在V生根它源自T的高度的各頂點v
首先選擇任意的底部R對於T,產生T(r)。掃描T(r)葉到根,爲每個頂點v存儲以v爲根的T(r)的子樹的高度,掃描T(r)根到葉,計算每個頂點v, T中從v開始的最長路徑的長度不能訪問v(相對於T(r))的恰當後代。這第二步有點棘手;你需要計算v和它的兄弟姐妹的最大和第二大高度,這可以重複用於v的兄弟姐妹。 T(v)的高度是其兩個標籤的最大值。