如何在以字典表示的图中进行深度优先搜索。

Question

这里是图表示为字典与我 。

{'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新手，需要帮助。

Answer 1

原始代码片段来自 这篇大文章. 这个实现使用生成器来获得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