Печать цикла в графике

Question

Я хотел бы найти любой цикл внутри графика и распечатать список, представляющий первый цикл, который я нашел.

Вот моя работа на данный момент:

def find_cycle(self):
    def aux(vertex, visited, parent, path):
        visited.add(vertex)
        neigh = self.neighbors_out(vertex)
        for n in neigh:
            if n not in visited:
                if aux(n, visited, parent, path):
                    path.append(n)
                    return True
            elif parent != n:
                path.append(n)
                return True
        return False

    vertices = self.vertices()
    visited = set()
    cycle = []
    while vertices:
        vertex = vertices.pop()
        if aux(vertex, visited, -1, cycle):
            return cycle
        vertices = vertices - visited

    return None

Я пытался используйте подход DFS и обновите путь, верните его, если это цикл. Он работает не очень хорошо, есть ли идея его улучшить?

Answer 1

Вы хотите выполнить поиск в ширину, а не в глубину. вы выбираете вершину root, и в каждой посещаемой вершине вы сохраняете путь от root к этой вершине (легко сделать рекурсивно). Когда вы, наконец, видите вершину, которую видели раньше, вы объединяете ее путь с тем, который у вас есть, и вот ваш цикл.