Алгоритм поиска наименьшего общего предка в дереве

[PsyHaSTe]

Деревом называется неориентированный связный граф из N вершин и N-1 ребер. Из любой вершины до любой другой существует ровно один простой путь.
Корнем дерева будет называться такая вершина, от которой задано направление движения по дереву при его обходе.

*зануда мод он*
Грамотное определение: «Дерево — это граф, который не имеет циклов».
Корень — это вершина, откуда достижимы все остальные вершины.
*зануда мод офф*

Иначе необходимо вершину a или b к корню.

глагол забыли.

В целом интересно. Спасибо за статью.

[fader44]

*зануда мод он*
> Грамотное определение: «Дерево — это граф, который не имеет циклов».

Каждое из двух первых предложений из цитаты статьи является грамотным определением дерева. А вот ваше определение — неверно (ниже написали почему). Все 3 определения равносильны, и все 3 — классические.

> Корень — это вершина, откуда достижимы все остальные вершины.

В дереве из любой вершины все остальные достижимы. И (внезапно!) любую вершину можно сделать корнем (если за нее подвесить). Так что корректно определять корень направлениями движений.
*зануда мод офф*

[andy_p]

> Грамотное определение: «Дерево — это граф, который не имеет циклов».

Ещё грамотнее «Дерево — это связный граф, который не имеет циклов».
Иначе получается лес деревьев.

[elw00d]

А я как-то столкнулся с такой задачей, и на коленке придумал вроде бы работающий алгоритм, интересно, можно ли найти пример, на которых он не сработает?

        public static Control FindCommonAncestor(Control a, Control b) {
            if (null == a)
                throw new ArgumentNullException("a");
            if (null == b)
                throw new ArgumentNullException("b");
            //
            List<Control> visited = new List<Control>();
            Control refA = a;
            Control refB = b;
            bool f = true;
            for (;;) {
                if (refA == refB)
                    return refA;
                if (visited.Contains(refB))
                    return refB;
                if (visited.Contains(refA))
                    return refA;
                if (refA.Parent == null && refB.Parent == null)
                    return null;
                if (f) {
                    if (refA.Parent != null) {
                        visited.Add(refA);
                        refA = refA.Parent;
                    }
                } else {
                    if (refB.Parent != null) {
                        visited.Add(refB);
                        refB = refB.Parent;
                    }
                }
                f = !f;
            }
        }

[elw00d]

Судя по википедии, я таким образом смастерил одну из вариаций на тему наивного алгоритма. Впрочем, в моем случае большего и не требовалось )

[halyavin]

Этот алгоритм часто используют на олимпиадах по программированию (так же как и дерево отрезков) для решения LCA. Слава богу, решений за O(1) пока не требуют.