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

Если у вас есть граф, представленный в виде списка смежности, как вы можете обнаружить какие-то odd length-ed циклы odd length-ed в python?

Предположим, у вас есть график, введенный как вход:

 A = { 1: [2, 4], 2: [1, 5], 3: [4, 5], 4: [1, 3, 5], 5: [2, 3, 4], 6: [] } V = { 1: <node>, 2: <node>, 3: <node>, 4: <node>, 5: <node>, 6: <node> } 

A – это словарь, в котором ключ – это число, а значение – список чисел, поэтому между ключом есть край, связанный со всеми его значениями. V – словарь, который отображает число в экземпляр узла.

Как вы можете определить, существует ли цикл с нечетной длиной?

Из вышеприведенного ввода фактически существует тот, который использует узлы 3, 4, 5 .

В принципе, как я могу получить вывод 3 4 5 ?

благодаря

Общим способом найти петлю на графике является использование алгоритма поиска по глубине . В вашем случае я бы пометил каждую вершину цифрами 1 и 2, так что все соседние вершины имеют разные числа. Если вы обнаружите, что есть две вершины с одинаковой меткой, это означает, что вы нашли цикл с нечетной длиной. Вот моя краткая реализация (я не использовал V dictionaty, предполагая, что A описывает график без as is):

 import sys A = { 1: [2, 4], 2: [1, 5], 3: [4, 5], 4: [1, 3, 5], 5: [2, 3, 4], 6: [] } num_vertices = len(A) sys.setrecursionlimit(num_vertices + 2) mark = [None] * (num_vertices + 1) cur_path = [] def DFS(vertex, cur_mark = 1): mark[vertex] = cur_mark global cur_path cur_path.append(vertex) for neighbour in A[vertex]: if not mark[neighbour]: DFS(neighbour, 3 - cur_mark) elif mark[neighbour] == cur_mark: print 'Found a loop of odd length: ', cur_path[cur_path.index(neighbour):] sys.exit(0) cur_path = cur_path[:-1] # Visit all connected components for vertex in xrange(1, num_vertices + 1): if not mark[vertex]: DFS(vertex) print 'Cycle of odd length not found'