找到最小化樹深度的根

給出一棵樹，內容無週期（例如最小生成樹：http://fr.wikipedia.org/wiki/Fichier:Minimum_spanning_tree.svg）如何計算哪個節點最小化樹深度（如果它用作根）？找到最小化樹深度的根

2012-03-30 luxcem

澄清：你問，給定完全連接的無向非循環圖，選擇距離最近的節點最近的節點？ – DRVic 2012-03-30 23:28:36

所有樹木都不包含週期。根據定義，樹是一個無週期的連通圖。如果有一個頂點，答案是微不足道的。所以假設至少有兩個頂點。

讓ù和v是兩個頂點，使得它們的距離d（ü，v）是最大的。應該很容易看出，如果一個選擇沿最短UV路徑頂點是根，深度將至少天花板（d（ü，v）/ 2）。還應當指出的是，如果一個選擇頂點是路徑上的根沒有，深度將大於天花板（d（ü，v）/ 2）。

假設我們選擇了根- [R爲沿着最小UV路徑，使得d中間頂點（ü，- [R）= 天花板（d（ü，v）/ 2）和d（- [R，v）≤ 天花板（d（u,v）/ 2）。如果有另一個頂點，瓦特，這樣d（[R，瓦特）>天花板（d（ü，v）/ 2），我們將不得不d（ü，- [R）< d（瓦特，- [R），然後，因爲有是在一個樹中的任何兩個不同的頂點之間只有一個路徑，我們有d（ü，v）= d（ü，- [R）+ d（- [R，v）< d（ü，- [R）+ d（- [R，瓦特）= d（ü，瓦特），這與該ù和v有最大的距離。所以，現在的深度，給定- [R爲根，是天花板（d（ü，v）/ 2）。

所以我們需要找到距離最遠的兩個頂點。一旦我們做到這一點，我們可以用最短路徑搜索算法UV，注意長度，並遍歷中途沿上述路徑和使用中的頂點作爲根。

我們如何找到這些頂點？選取頂點w並將其放入隊列中。當隊列非空時，將隊列中下一個頂點的鄰居添加到隊列末尾。當隊列爲空時，請記下最近移除的頂點。這將是ü。再次執行該程序，您將有訴。

爲什麼這樣嗎？上述算法找到距離最遠的頂點w。如果瓦特恰好是ü或v，該算法顯然沒有分別v或ü。因此，假設瓦特既不是ü也不v。如果算法在第一遍中發現了或或v，那麼它又會起作用（因爲它會在第二遍中找到另一個），所以假設通過相反的方式在第一遍之後找到x，使得它不是樹的最大路徑的末端。從三角不等式，我們有d（ü，v）≤ d（ü，瓦特）+ d（瓦特，v）和d（v，x）≤ d（v,w）+ d（w,x）。從減去第二，第一，我們有d（ü，v） - d（v，X）≤ d（ü，瓦特） - d （w,x）。然後，我們可以重新安排到d（ü，v）+ d（瓦特，X）≤ d（ü，瓦特）+ d（v，x）。由於d（瓦特，Ú）≤ d（瓦特，X）（X是從瓦特的最大路徑的端部; 武不能超過WX ）和d（v,x）< d（ ü，v）（X不是最大路徑的結束），我們可以強化不平等d（ü，v）+ d（瓦特，X）< d（ü，v）+ d（瓦特，x）。但這不可能，所以x必須在最大路徑的末尾。

來源

2012-03-30 23:33:03

謝謝！沒有其他方法？ – luxcem 2012-03-31 21:32:08

我的算法/方法與Saeed完全一樣。我只是給出了一個解釋/證明，以便你可以閱讀並知道我的答案是正確的。我可以嘗試考慮一種替代算法/方法。這個有什麼問題？ – 2012-03-31 22:18:27

這個問題沒有問題，它完美的工作，但我想知道是否有其他方法可以做到這一點（只是出於好奇） – luxcem 2012-05-11 12:36:52

找到樹的diameter後選擇直徑的中間節點作爲根。爲了找到運行兩個BFS的直徑，第一個BFS從隨機節點v開始，並從v找到最遠的節點，將其命名爲x，第二個BFS從x找到最遠的節點，其命名爲y。現在x和y之間的路徑是直徑。

來源

2012-03-31 01:14:21

@nax，代碼的哪一部分，如果你有一個很好的數據結構，你可以簡單地使用任何的Web上可用的樣本BFS代碼。 – 2012-03-31 02:48:47

對不起，我的英文，我的意思是不是來源 – luxcem 2012-03-31 10:03:24

@nax，我的英文不比你好，但你想參考哪個部分？你是否在尋找證據（並不難，最好自己嘗試）。但這是一種民間傳說和衆所周知的問題和解決方案。 – 2012-03-31 21:35:52

我認爲下面的算法可能工作（我沒有驗證它），從圖的任何樹表示開始。

S = set of all leaves of the tree 
foreach node in S: mark(node) 
repeat: 
    # at each iteration, S is the set of all nodes at 
    # a given min distance to a leave 
    # initially this distance is 0, then 1, etc. 
    S' = empty set 
    foreach node in S: 
    parent = parent(node) 
    if !marked(parent): S' += parent; mark(parent) 
    if S' is empty then S contains all innermost nodes, we are done 
    S = S' and continue

來源

2012-03-31 01:47:49

找到最小化樹深度的根

回答

相關問題