0

Как можно узнать, содержит ли неориентированный граф G(V, E) цикл за O(|V|)? Достаточно выяснить факт наличия цикла без его вывода.

17
  • 2
    Терзают меня смутные сомнения, что без просмотра ребер это не получится...
    – Harry
    22 ноя 2021 в 9:18
  • @Harry из вопроса не следует, что ни одно ребро не должно быть просмотрено, если что
    – warmonger
    22 ноя 2021 в 9:34
  • Должно быть просмотрено не более О(1) ребер для каждой вершины, нет?
    – Harry
    22 ноя 2021 в 9:48
  • Топологическая сортировка, которая откажет при наличии цикла, тоже работает за O(|V|+|E|)...
    – Harry
    22 ноя 2021 в 9:54
  • 1
    русские переводы всегда нужно проверять по оригиналам. иначе можно выучить не то. Я до сих пор помню, как функции почему то кричали (call) :)
    – KoVadim
    22 ноя 2021 в 11:38

1 ответ 1

1

Сдаётся мне после поправки на "неориентированный", что дело в следующем - неорграф, не имеющий циклов, является деревом.

А у дерева количество рёбер на единицу меньше количества узлов. Поэтому для каждого из компонентов графа должно выполняться соотношение E<V - это можно проверить любым обходом.

В данном случае (не обходим все рёбра, если их много, а останавливаемся на V-ом):

O(V + E) = O(V+V) = O(V)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.