Как определить наличие цикла в неориентированном графе?
Как можно узнать, содержит ли неориентированный граф G(V, E) цикл за O(|V|)? Достаточно выяснить факт наличия цикла без его вывода.
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Сдаётся мне после поправки на "неориентированный", что дело в следующем - неорграф, не имеющий циклов, является деревом.
А у дерева количество рёбер на единицу меньше количества узлов. Поэтому для каждого из компонентов графа должно выполняться соотношение E<V - это можно проверить любым обходом.
В данном случае (не обходим все рёбра, если их много, а останавливаемся на V-ом):
O(V + E) = O(V+V) = O(V)