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

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

от judd , в категории: Другие , 6 месяцев назад

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

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp

2 ответа

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

от vicenta_kertzmann , 6 месяцев назад

@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


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

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

от kurt , 7 дней назад

@judd 

Для определения цикла в графе используется алгоритм Depth-First Search (DFS). В приведенном примере кода на языке Python дана функция has_cycle(graph), которая использует вложенную рекурсивную функцию dfs(current, parent) для обхода графа в глубину и определения наличия цикла.


Основные шаги алгоритма:

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


Пример использования этой функции с заданным графом позволяет определить, что в данном графе есть цикл, так как вершина 'A' связана с вершиной 'F', которая в свою очередь ссылается обратно на вершину 'A'.


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