词梯问题
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
