Какой алгоритм находит диаметр некорневого недвоичного дерева?

Question

При наличии неориентированного некорневого недвоичного дерева мы должны найти один из диаметров этого дерева в кратчайшие сроки без использования рекурсивных методов.

Я видел много разных ответов и хотел бы получить ясность по поводу того, что правильно. Когда вам дается неориентированное недроеченное недвоичное дерево, можете ли вы запустить BFS в любой вершине A, чтобы получить самую дальнюю вершину B из этого, а затем запустить BFS на этом узле B, что приведет к диаметру между B и полученным C?

Помимо этого, если это действительно правильно, какова сложность времени? Я видел O (E) и O (E + V)

Answer 1

Я видел много разных ответов и хотел бы получить ясность по поводу того, что является правильным.Когда вам дается неориентированное не-корневое не двоичное дерево, можете ли вы запустить BFS в любой вершине A, чтобы получить самую дальнюю вершину B из этого, а затем запустить BFS на этом узле B, что приведет к диаметру между B и полученным C?

Да, этот алгоритм правильный, тогда d(B, C) - это диаметр дерева.Вы можете найти больше информации об этом алгоритме (и почему он работает) на этом посте .

Помимо этого, если это действительно правильно, какова сложность времени?Я видел O (E) и O (E + V)

Вы дважды запускаете BFS на дереве.Каждая BFS имеет временную сложность O(V), поскольку каждая вершина посещается ровно один раз.
В дереве всегда проверяется равенство E = V-1, поэтому для любого алгоритма, работающего на дереве, O(V) = O(E) = O(E + V), поэтому обе записиверны.O(V) лучше ИМХО, ради простоты и ясности.