цикл вывода входного словаря теории графов, если существует - PullRequest
Новая
       9

цикл вывода входного словаря теории графов, если существует

0 голосов
/ 04 октября 2018

То, что я написал ниже, - это функция, позволяющая определить, может ли график (показанный в форме словаря) с заданной начальной точкой (которая также является конечной точкой) образовывать окружность.Например, график = {1: [2,3,4], 2: [1,5,6], 3: [1,7,8], 4: [1,9], 5: [2],6: [2], 7: [3], 8: [3,9], 9: [4,8]}. Если начальная точка равна 3, мы можем найти круг: 3-1-4-9-8-3, однако, если начальная точка 7, круг не будет найден.Мой код теперь дает только True, если круг существует, и [] пустой список, если его нет.Что если я захочу вернуть круг (не нужно быть самым длинным или самым коротким кругом, просто любой, который соответствует требованию)?Я не уверен, смогу ли я думать и кодировать таким образом, поскольку цель изменилась.

'' 'вход: график и начальная точка; выход: функция списка: определить, существует ли круг с заданной точкой в ​​качестве начальной и конечной точек' '' 

def cycle(graph,start_point):
    queue=[start_point]
    visited=set()
    visited.add(queue[0])
    while queue:
        from_point=queue.pop() #DFS
        for to_point in graph[from_point]:
            if to_point in visited:
                return True
            else:
                queue.append(to_point)
                visited.add(to_point)
            graph[to_point].remove(from_point)
    return []
...