2

ツリーに存在する各ノードの隣接リストを知っている場合、そのツリーに存在する 2 つのノードの共通の最下位の祖先を見つけるにはどうすればよいでしょうか?

実際には、任意の 2 つのノード間の距離を調べたいので、LCA を計算したいと考えています。隣接リストから計算する方法はありますか?

T の n1 と n2 の LCA は、ルートから最も離れた n1 と n2 の共有先祖です。最小共通祖先の計算は、たとえば、ツリー内のノードのペア間の距離を決定する手順の一部として役立つ場合があります。n1 から n2 までの距離は、ルートから n1 までの距離に距離を加えたものとして計算できます。ルートから n2 まで、ルートから最も低い共通の祖先までの距離の 2 倍を引いたものです。（ソースウィキ）

4

3 に答える 3

1

隣接リストを扱っているという事実は、実際には問題を変えません。

ノード A と B の LCA を求める基本的な考え方は次のとおりです。

  • ルートから開始します。
  • 子のサブツリーに A と B の両方が含まれている場合、そのサブツリーの LCA を返します。
  • 子に A が含まれ、別の子に B が含まれている場合。

上記のチェックは、どちらの場合でもインジケーターを返すことにより、単一の関数に簡単に組み込むことができます。

順序付けられていないツリーでは、最悪の場合、ツリー全体を探索する必要がありますが、二分探索ツリーでは、その値を現在のノードと比較するだけで、左または右のサブツリーにノードが含まれているかどうかを簡単に確認できます。

しかし実際には、LCA アルゴリズムを使用して距離を決定するべきではありません。代わりに、LCA の代わりに距離を返すように上記を変更する必要があります。これを行うための変更はかなり単純です。

  • 子のサブツリーで既に距離を見つけたら、それを返します。
  • A と B の両方が別々の子のサブツリーにある場合は、A と B の間の距離を返します。
  • 子のサブツリーで A または B のいずれかしか見つからない場合は、A または B までの距離を返し、何を返すかを示すインジケーターを付けます。
于 2013-09-28T11:37:48.543 に答える
0

次のようなものを試すことができます：

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-28T11:37:35.850 に答える
0
  1. 各ノードの高さ (ルートからの距離) を維持します。
  2. 2 つのノードの高さが異なる場合は、ノードが同じレベルになるまで、深いノードから上に移動します。
  3. 2 つのノードが等しい場合、答えが得られます。そうでない場合は、別のレベルに移動して繰り返します。

これは、ツリーがルート化されたものであり、各ノードの高さと親ポインターを格納するための少し余分なスペースに対応できることを前提としています。

このアルゴリズムの効率は O(高さ) であるため、ツリーのバランスに依存します。

于 2013-09-29T05:27:39.763 に答える