如何在表示为字典的图中执行深度优先搜索

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

原始代码片段取自this great article。此实现使用生成器通过 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

如何在表示为字典的图中执行深度优先搜索

How to perform depth first search in graph represented as dictionary

python

depth-first-search

python-3.x