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

Общим способом найти петлю на графике является использование алгоритма поиска по глубине . В вашем случае я бы пометил каждую вершину цифрами 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'