Как определить наличие цикла в неориентированном графе?

@judd 

Для определения наличия цикла в неориентированном графе можно использовать алгоритм обхода графа в глубину (Depth-First Search, DFS).

1. Начните с выбора произвольной вершины в графе.
2. Пометьте текущую вершину как посещенную.
3. Рекурсивно пройдитесь по всем соседним вершинам текущей вершины.
4. Если соседняя вершина уже посещена и не является родительской для текущей вершины, то в графе есть цикл.
5. Если соседняя вершина еще не посещена, рекурсивно пройдитесь по ней. Если в результате обхода найден цикл, то верните значение True.
6. Если после обхода всех соседних вершин цикл не найден, то верните значение False.

Пример кода на языке Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def has_cycle(graph):
    visited = set()

    def dfs(current, parent):
        visited.add(current)

        for neighbor in graph[current]:
            if neighbor not in visited:
                if dfs(neighbor, current):
                    return True
            elif neighbor != parent:
                return True

        return False

    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex, None):
                return True

    return False

Пример использования:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

graph = {
    'A': {'B', 'F'},
    'B': {'A', 'C'},
    'C': {'B', 'D'},
    'D': {'C'},
    'E': {'F'},
    'F': {'A', 'E'}
}

print(has_cycle(graph))  # True

Таким образом, данный алгоритм позволяет определить наличие цикла в неориентированном графе.