Python - 图数据结构 - 如何正确实现广度优先搜索以找到可达顶点

Question

在Python中，我有一个图（Graph）类，这个类里面有一个存放顶点对象的字典。每个顶点对象都有一个边的字典（边包括起始节点、结束节点和权重……可以想象成一支箭头指向另一个节点，箭头上有一个表示旅行成本的数字）。

通过这些类，我正在绘制一个图，表示飞机从一个城市飞到另一个城市所需的时间。根据这个图，我需要用Dijkstra算法找出两个节点之间的最短路径（最快的路径）。我还需要找出从一个起始顶点可以到达的所有顶点。

我可以在图中完美地添加和删除边（因此也能添加节点）。但是，我就是想不出一个简单的方法来用我创建的数据结构实现Dijkstra算法或者广度优先搜索（用来找出可到达的顶点）。

如果有人能建议我该如何修改或实现这些算法，使它们能正确工作，我将非常感激。这是我已经花了将近一周时间，每天花很多小时在做的作业，我就是过不去这个难关。再次感谢任何建议或帮助。我并不指望有人为我写代码，但伪代码会很有帮助（而且我不能仅仅从维基百科复制粘贴伪代码，因为我已经试过了）。

Answer 1

你的代码太复杂了。

先从实现基本功能的简单代码开始，然后再逐步添加其他功能。为了帮助你入门，我会分享一些处理图形时简单但基本的代码。

from collections import deque

class fringe(object):
    def __init__(self, kind= 'stack'):
        f= deque()
        self._p= f.append if kind is 'stack' else f.appendleft
        self._f= f

    def __call__(self, item):
        self._p(item)
        return self

    def __iter__(self):
        while len(self._f):
            item= self._f.pop()
            yield item

    def __repr__(self):
        return self._f.__repr__().replace('deque', 'fringe')

def paths(G, start, terminal, F= fringe()):
    for node, path in F((start, [start])):
        for node in G[node]:
            if node is terminal:
                yield path+ [terminal]
            elif node not in path:
                F((node, path+ [node]))

还有一个测试：

if __name__ == '__main__':
    a, b, c, d, e, f= 'A', 'B', 'C', 'D', 'E', 'F'
    G= {a: [b, c], b: [c, d], c: [d], d: [c], e: [f], f: [c]}
    print 'All paths from:', a, 'to:', d
    print 'BFS'
    for path in paths(G, a, d): print path
    print 'DFS'
    for path in paths(G, a, d, fringe('queue')): print path

运行后会产生：

All paths from: A to: D
BFS
['A', 'C', 'D']
['A', 'B', 'D']
['A', 'B', 'C', 'D']
DFS
['A', 'B', 'D']
['A', 'C', 'D']
['A', 'B', 'C', 'D']