Comments 6
Деревом называется неориентированный связный граф из N вершин и N-1 ребер. Из любой вершины до любой другой существует ровно один простой путь.
Корнем дерева будет называться такая вершина, от которой задано направление движения по дереву при его обходе.
*зануда мод он*
Грамотное определение: «Дерево — это граф, который не имеет циклов».
Корень — это вершина, откуда достижимы все остальные вершины.
*зануда мод офф*
Иначе необходимо вершину a или b к корню.
глагол забыли.
В целом интересно. Спасибо за статью.
*зануда мод он*
> Грамотное определение: «Дерево — это граф, который не имеет циклов».
Каждое из двух первых предложений из цитаты статьи является грамотным определением дерева. А вот ваше определение — неверно (ниже написали почему). Все 3 определения равносильны, и все 3 — классические.
> Корень — это вершина, откуда достижимы все остальные вершины.
В дереве из любой вершины все остальные достижимы. И (внезапно!) любую вершину можно сделать корнем (если за нее подвесить). Так что корректно определять корень направлениями движений.
*зануда мод офф*
> Грамотное определение: «Дерево — это граф, который не имеет циклов».
Каждое из двух первых предложений из цитаты статьи является грамотным определением дерева. А вот ваше определение — неверно (ниже написали почему). Все 3 определения равносильны, и все 3 — классические.
> Корень — это вершина, откуда достижимы все остальные вершины.
В дереве из любой вершины все остальные достижимы. И (внезапно!) любую вершину можно сделать корнем (если за нее подвесить). Так что корректно определять корень направлениями движений.
*зануда мод офф*
> Грамотное определение: «Дерево — это граф, который не имеет циклов».
Ещё грамотнее «Дерево — это связный граф, который не имеет циклов».
Иначе получается лес деревьев.
Ещё грамотнее «Дерево — это связный граф, который не имеет циклов».
Иначе получается лес деревьев.
А я как-то столкнулся с такой задачей, и на коленке придумал вроде бы работающий алгоритм, интересно, можно ли найти пример, на которых он не сработает?
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;
}
}
Судя по википедии, я таким образом смастерил одну из вариаций на тему наивного алгоритма. Впрочем, в моем случае большего и не требовалось )
Этот алгоритм часто используют на олимпиадах по программированию (так же как и дерево отрезков) для решения LCA. Слава богу, решений за O(1) пока не требуют.
Sign up to leave a comment.
Алгоритм поиска наименьшего общего предка в дереве