词梯问题

from myGraph import Graph,Vertex
from myqueue import Queue

def buildGraph(file):
    d = {}
    g = Graph()

    with open(file) as f:
        for line in f:
            word = line[:-1]
            for i in range(len(word)):
                bucket = word[:i] + '_' + word[i+1:]
                if bucket in d:
                    d[bucket].append(word)
                else:
                    d[bucket] = [word]

    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1, word2)

    return g

def bfs(g, start):
    start.setDistance(0)
    start.setPred(None)
    vertexQueue = Queue()
    vertexQueue.enqueue(start)
    while vertexQueue.size() > 0:
        currentVertex = vertexQueue.dequeue()
        for nbr in currentVertex.getConnections():
            if nbr.getColor() == 'White':
                nbr.setColor('Gray')
                nbr.setDistance(currentVertex.getDistance() + 1)
                nbr.setPred(currentVertex)
                vertexQueue.enqueue(nbr)
        currentVertex.setColor('Black')

def traverse(w):
    print(w.getDistance())
    x = w
    while x.getPred():
        print(x.getId())
        x = x.getPred()
    print(x.getId())


if __name__ == '__main__':
    g = buildGraph('fourletterwords.txt')
    # for i in g:
    #     print(i)
    bfs(g, g.getVertex('FOOL'))
    traverse(g.getVertex('SAGE'))

输出：

6
SAGE
SALE
SALL
MALL
MOLL
MOOL
FOOL