← Назад к списку задач

цикл в неориентированном графе dfs

Структуры данных Уровень 3

Описание задачи

Необходимо реализовать функцию для определения, содержит ли неориентированный граф цикл. Функция должна проверить все вершины графа и обнаружить замкнутые пути во время обхода в глубину (DFS).

Вход:
g: Словарь, представляющий неориентированный граф. Ключи словаря - это вершины графа, а значения - списки смежных вершин. Например, {1: [2, 3], 2: [1, 4], 3: [1], 4: [2]} представляет граф с вершинами 1, 2, 3 и 4, где 1 связана с 2 и 3, 2 связана с 1 и 4, 3 связана с 1, а 4 связана с 2.

Выход:
True, если в графе есть цикл; False в противном случае.

Режим обучения Готово

Объяснение решения уже подготовлено. Нажмите кнопку, чтобы посмотреть.

Ваше решение

Подсказка (готовое решение)

def has_cycle_undirected(g):