最小直徑生成樹算法

Question

給定一個無向和連通圖G，找到直徑最小的生成樹。

Answer 1

singhsumit將相關論文鏈接到Hassin and Tamir，標題爲「關於最小直徑生成樹問題」，但他的答案目前已被刪除。本文的主要思想是在無向圖中找到最小直徑生成樹可以通過找到圖的「絕對1中心」並返回根植於其中的最短路徑樹來實現。

絕對1中心是指頂點或邊緣上的點，從該點到最遠頂點的距離最小。這可以通過Kariv和Hakimi（網絡定位問題的一種算法方法，I：p-中心）算法或早期的Hakimi，Schmeichel和Pierce算法（網絡中的p-中心）找到，我將試圖從運行時間和幾十年的事後重建。 （愚蠢的薪水牆。）

使用Floyd-Warshall或Johnson的算法計算所有對距離。對於每個邊u-v，按如下方式在該邊上找到1中心的最佳候選。

設邊u-v上的點由從0（u本身）到len（u-v）（v本身）範圍內的μ索引。從指數μ處的點到頂點w的距離爲

min（μ+ d（u，w），len（u-v）-μ+ d（v，w））。

作爲μ的函數，這個量在

增加後減少，在最大

μ=（LEN（U - V）+ d（V，W） - d（ u，w））/ 2。

按此argmax對頂點排序。對於數組中的每個分區，將其分爲左側子數組和右側子數組，計算引起相同argmax分區的μ的時間間隔[a，b]。將此區間與[0，len（u - v）]相交;如果十字路口是空的，然後繼續前進。否則，從由u索引的點開始的左子陣列中找出最大距離L，並從由u索引的點開始的右子陣列中的最大距離R索引b。 （計算這些最大值的成本可以分攤到每個分區的O（1），通過從左到右和從右到左的掃描開始。）最佳選擇是[a，b]中的μ使最大值（L - （μ - ​​a），R +（b - μ））最小化。