python-3.x - 在 Python 3 中实现呼吸优先搜索（如何将 'Set' 转换为 'Dictionary'

Question

大家好，我开始学习 Python。我使用字典图的呼吸优先搜索方式是错误的。我有一个错误，我的代码是

graphs = {
    'a': {'b': 3, 'c': 4, 'd': 7},
    'b': {'c': 1, 'f': 5},
    'c': {'f': 6, 'd': 2},
    'd': {'e': 3, 'g': 6},
    'e': {'g': 3, 'h': 4},
    'f': {'e': 1, 'h': 8},
    'g': {'h': 2},
    'h': {'g': 2}
}

我在这里尝试过。

def bfs_paths(graphs, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graphs[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))
    return queue

def shortest_path(graph, start, goal):
    try:
        return next(bfs_paths(graph, start, goal))
    except StopIteration:
        return None

print(shortest_path(graphs, 'a', 'c'))

Answer 1

你确实是正确的假设操作

graphs[vertex] - set(path)

字典和集合之间无效。Python 需要一些默认的（并且可能是非直观的）行为来使用字典键或值来实现这样的集合差异。而是尝试将您的 for 循环更改为：

for next in graphs[vertex]:
        if next in set(path):
            continue

这将达到您正在寻找的结果。