ПРОВЕРКА НА ЦИКЛИЧНОСТЬ ГРАФА PYTHON

В программировании граф используется для представления связей между объектами. Одним из основных вопросов, которые могут возникнуть при работе с графом, является проверка наличия циклов, то есть замкнутых маршрутов в графе.

Для проверки наличия циклов в графах можно использовать алгоритм обхода графа в глубину и отслеживать наличие обратных ребер при проходе. Для этого можно использовать следующий код на Python:

def check_cycle(graph):    visited = set()    stack = set()    for node in graph:        if node not in visited:            if dfs_cycle(graph, node, visited, stack):                return True    return Falsedef dfs_cycle(graph, start_node, visited, stack):    visited.add(start_node)    stack.add(start_node)    for neighbor in graph[start_node]:        if neighbor not in visited:            if dfs_cycle(graph, neighbor, visited, stack):                return True        elif neighbor in stack:            return True    stack.remove(start_node)    return False

В этом коде функция check_cycle принимает словарь, представляющий граф, и возвращает логический результат проверки наличия цикла. Функция dfs_cycle реализует алгоритм обхода в глубину с отслеживанием обратных ребер.