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

Пользователь

от judd , в категории: Другие , 23 дня назад

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

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp

1 ответ

Пользователь

от vicenta_kertzmann , 22 дня назад

@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


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