Лучший алгоритм, чтобы определить, является ли неориентированный граф деревом

Question

Какова временная сложность алгоритма Best для определения того, является ли неориентированный граф деревом?

можно ли сказать Big-oh (n) с n вершинами ??

Answer 1

Да, это O (n). При поиске по глубине в ориентированном графе имеется 3 типа не-древесных ребер - поперечное, обратное и прямое.

Для неориентированного случая единственным видом не-древесного края является задний край. Итак, вам просто нужно искать задние края.

Короче, выберите начальную вершину. Пройдите и продолжайте проверять, является ли встречный край задним. Если вы найдете n-1 ребер дерева, не найдя задних ребер, а затем, выбегая из ребер, вы - золото.

(Просто для пояснения - back edge - это тот, где вершина на другом конце уже встречалась - и из-за свойств неориентированных графов вершина на другом конце будет предком данного узла в дерево, которое строится.)

Answer 2

Да, это O (n).

Выберите начальный узел и выполните первый обход глубины.Если вы посещаете узел более одного раза, это не дерево.