查找鄰接列表中兩個節點的最低公共祖先

如果我知道樹中每個節點的鄰接列表，那麼如何找出該樹中存在的任何兩個節點的最低公共祖先？查找鄰接列表中兩個節點的最低公共祖先

其實我想找出任意兩個節點之間的距離，所以我想計算LCA。有沒有辦法從鄰接表中計算出它？

T中n1和n2的LCA是距離根最遠的n1和n2的共享祖先。最低共同祖先的計算可能是有用的，例如，作爲確定樹中節點對之間距離的過程的一部分：從n1到n2的距離可以計算爲從根到n1的距離，加上距離從根到n2，減去從根到最低共同祖先距離的兩倍。（Source Wiki）

來源

2013-09-28 TSP1993

您可以嘗試類似：

class Node 
{ 
public: 
    // Other stuff. 
    const Node* getParent() const { return parent; } 
private: 
    Node* parent; 
    std::vector<Node*> children; 
}; 

const Node* getLowestCommonAncestor(const Node& lhs, const Node& rhs) 
{ 
    for (const Node* node1 = &lhs; node1 != nullptr; node1 = node1->getParent()) { 
     for (const Node* node2 = &rhs; node2 != nullptr; node2 = node2->getParent()) { 
      if (node1 == node2) { 
       return node1; 
      } 
     } 
    } 
    return nullptr; 
}

，或者如果你沒有父：

namespace detail 
{ 
    struct LCAFlag { 
     enum { NoFound = 0, leftFound = 1, rightFound = 2 }; 
    }; 

    const Node* getLCA_Rec(const Node& root, const Node& lhs, const Node& rhs, unsigned int& flag) 
    { 
     if (&root == &lhs) { 
      flag |= LCAFlag::leftFound; 
     } else if (&root == &rhs) { 
      flag |= LCAFlag::rightFound; 
     } 
     if (flag == (LCAFlag::leftFound | LCAFlag::rightFound)) { 
      return nullptr; // both found. parent is the LCA 
     } 
     for (auto it = root.children.begin(); it != root.children.end(); ++it) { 
      const Node* res = getLCA_Rec(**it, lhs, rhs, flag); 

      if (res != nullptr) { 
       return res; 
      } 
      if (flag == (LCAFlag::leftFound | LCAFlag::rightFound)) { 
       return &root; 
      } 
     } 
     return nullptr; 
    } 
} 
const Node* getLCA(const Node& root, const Node& lhs, const Node& rhs) 
{ 
    unsigned int flag = detail::LCAFlag::NoFound; 
    return detail::getLCA_Rec(root, lhs, rhs, flag); 
}

來源

2013-09-28 11:37:35 Jarod42

只是代碼沒有解釋？ – Dukeling

認真應該有這個解釋 – TSP1993

，我們正在處理一個鄰接表的事實沒有按」真的改變了這個問題。

的基本思想來查找節點A的LCA和B如下：

開始從根。
如果孩子的子樹同時包含A和B，則返回該子樹的LCA。
如果一個孩子包含A和另一個子含有B.

上述檢查可以相當容易被結合到單一的功能通過返回對於任一種情況下的一個指標。

在一個無序的樹中，你必須在最壞的情況下探索整個樹，但是在二叉搜索樹中，你可以通過簡單地比較它的值和當前值來檢查一個左右子樹是否可以包含一個節點節點。

但實際上你不應該使用LCA算法來確定距離。您應該修改上述以返回距離而不是LCA。這樣做的修改相當簡單：

當您已經在子樹的子樹中找到距離時，只需返回即可。
如果在單獨的子樹的子樹中找到A和B，則返回A和B之間的距離。
如果您只在子樹的子樹中找到A或B，則只需將距離返回到A或B用指示器說出你要回來的東西。

來源

2013-09-28 11:37:48 Dukeling

保持每個節點的高度（距離根的距離）。
如果兩個節點的高度不同，請從較深的節點向上走，直到節點處於同一級別。
如果兩個節點相同，那麼我們已經得到了我們的答案。如果沒有，再上一層並重復。

這是假定你的樹是紮根之一，你可以容納一些額外的空間來存儲每個節點的高度和家長指針。

該算法的效率是O（高度），所以它取決於樹的平衡程度。

來源

2013-09-29 05:27:39

查找鄰接列表中兩個節點的最低公共祖先

回答

相關問題