Цикл — это путь, возвращающийся в ту же вершину. Иногда цикл нормален (дорожная сеть), а иногда это ошибка: циклическая зависимость пакетов, взаимная блокировка процессов (deadlock), порядок задач, замкнувшийся в кольцо связный список. Как искать цикл — зависит от типа графа.

Обратное ребро в неориентированном графе, ромб и кольцо в ориентированном
Обратное ребро в неориентированном графе, ромб и кольцо в ориентированном

Неориентированный граф

Через DFS: если из вершины есть ребро в уже посещённую вершину, не являющуюся родителем, значит есть цикл. Родителя исключаем, потому что неориентированное ребро идёт в обе стороны. (См. тему DFS.)

python
def has_cycle(graph):
    seen = set()

    def dfs(node, parent):
        seen.add(node)
        for nxt in graph[node]:
            if nxt == parent:
                continue                 # the edge we came by is not a cycle
            if nxt in seen or dfs(nxt, node):
                return True
        return False

    return any(node not in seen and dfs(node, None) for node in graph)

tree = {1: [2, 3], 2: [1], 3: [1, 4], 4: [3]}
loop = {1: [2, 3], 2: [1, 3], 3: [1, 2, 4], 4: [3]}
print("tree:", has_cycle(tree))
print("loop:", has_cycle(loop))
text
tree: False
loop: True