@judd
Для определения наличия цикла в неориентированном графе можно использовать алгоритм обхода графа в глубину (Depth-First Search, DFS).
Пример кода на языке 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 |
Таким образом, данный алгоритм позволяет определить наличие цикла в неориентированном графе.
@judd
Для определения цикла в графе используется алгоритм Depth-First Search (DFS). В приведенном примере кода на языке Python дана функция has_cycle(graph)
, которая использует вложенную рекурсивную функцию dfs(current, parent)
для обхода графа в глубину и определения наличия цикла.
Основные шаги алгоритма:
Пример использования этой функции с заданным графом позволяет определить, что в данном графе есть цикл, так как вершина 'A' связана с вершиной 'F', которая в свою очередь ссылается обратно на вершину 'A'.
Данный алгоритм - один из способов проверки наличия цикла в графе и может быть полезным при решении задач, связанных с анализом графовых структур.