Как выполнить поиск по глубине в графе, представленном в виде словаря - PullRequest
Новая
       47

Как выполнить поиск по глубине в графе, представленном в виде словаря

0 голосов
/ 25 апреля 2020

Вот график, представленный в виде словаря со мной: 

{'A': {'C': 4, 'B': 5}, 
   'C': {'A': 4, 'B': 2, 'D': 10, 'F': 6}, 
   'B': {'A': 5, 'C': 2, 'D': 3}, 
   'E': {'F': 1}, 
   'D': {'C': 10, 'B': 3}, 
   'F': {'C': 6, 'E': 1}}

Мне нужно выполнить DFS от одного узла к другому и получить все веса по краям. Также от одного узла к другому может быть только один путь. Я новичок в python и мне нужна помощь.

1 Ответ

0 голосов
/ 25 апреля 2020

Оригинальный фрагмент кода взят из этой замечательной статьи . Эта реализация использует генератор для получения путей с помощью DFS. Я немного обновил его, чтобы получить значения весов для каждого пути. 

graph = {
    'A': {'C': 4, 'B': 5},
    'C': {'A': 4, 'B': 2, 'D': 10, 'F': 6},
    'B': {'A': 5, 'C': 2, 'D': 3},
    'E': {'F': 1},
    'D': {'C': 10, 'B': 3},
    'F': {'C': 6, 'E': 1}
}

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        (vertex, path) = stack.pop()
        for next in set(graph[vertex]) - set(path):
            if next == goal:
                yield path + [next]
            else:
                stack.append((next, path + [next]))

def get_weights(graph, path):
    value = 0
    node = graph[path[0]]
    for item in path[1:]:
        value += node[item]
        node = graph[item]
    return value

for path in dfs_paths(graph, 'A', 'F'):
    print(path, get_weights(graph, path))

### ['A', 'B', 'D', 'C', 'F'] 24
### ['A', 'B', 'C', 'F'] 13
### ['A', 'C', 'F'] 10
...