word ladder in python

代码多是参照这里的：首先是Graph 和Vertex 类

class Vertex:
    def __init__(self,key,distance=0,pred=None,color="white"):
        self.id=key
        self.connectedTo={} #dict which contains all the other vertices it is connected to
        self.pred=pred                  #for BFS tree/a list because we are dealing with cycles
        self.color=color                #for BFS tree
        self.distance=distance

    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr]=weight

    def __str__(self):
        return str(self.id)+' connectedTo: '+str([x.id for x in self.connectedTo])

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self,nbr):
        return self.connectedTo[nbr]

    def setPred(self,node):
        self.pred=node

    def getPred(self):
        return self.pred

    def setDistance(self,distance):
        self.distance=distance

    def getDistance(self):
        return self.distance

    def setColor(self,color):
        self.color=color

    def getColor(self):
        return self.color


#adjacency list implemented of the graph
class Graph:
    def __init__(self):
        self.vertList={}
        self.numVertices=0

    def addVertex(self,key):
        self.numVertices=self.numVertices+1
        newVertice=Vertex(key)
        self.vertList[key]=newVertice
        return newVertice

    def getVertex(self,n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def __contains__(self,n):
        return n in self.vertList

    def addEdge(self,f,t,cost=0):
        if f not in self.vertList:
            nv=self.addVertex(f)
        if t not in self.vertList:
            nv=self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t],cost)

    def getVertices(self):
        return self.vertList.keys()

    def __iter__(self):
        return iter(self.vertList.values())

下面是具体的实现。words.txt 是由4个字母组成的单词共有3686个，每行一个。

wc -l words.txt
3685 words.txt

#build thw word Ladder Graph
def buildGraph(wordFile="words.txt"):
    d={}
    g=Graph()
    wfile=open(wordFile,"r")
    #create bucket of words that differ by one letter
    for line in wfile:
        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]

    #add vertices and edges for words in the same bucket
    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 test_buildGraph():
    g=buildGraph()
    for v in g:
        print(v)
        #for w in v.getConnections():
        #    print(v.getId(),w.getId())

#test_buildGraph()

#BFS traverse Graph
def bfs(g,start):
    start.setDistance(0)
    start.setPred(None)
    vertQueue=[]
    vertQueue.append(start)
    while len(vertQueue) > 0:
        currentVert=vertQueue.pop(0)
        for nbr in currentVert.getConnections():
            if (nbr.getColor()=='white'):
                nbr.setColor("gray")
                nbr.setDistance(currentVert.getDistance()+1)
                nbr.setPred(currentVert)
                vertQueue.append(nbr)
        currentVert.setColor('black')


def bfs2(g,start,stop):
    parents={}
    q=[]
    q.append(start)
    parents[start.id]=None

    while len(q)> 0:
        node=q.pop(0)
        for neighbour in node.getConnections():
            n=neighbour.id

            if n not in parents:
                parents[n]=node.id
                if n==stop.id:
                    return parents
                q.append(neighbour)
    return parents


def traverse(y):
    #y: vertex
    x=y
    while(x.getPred()):
        print(x.getId())
        x=x.getPred()
    print(x.getId())

def test_traverse_with_bfs():
    g=buildGraph()
    start=g.getVertex("fool")
    bfs(g,start)
    traverse(g.getVertex("sage"))

test_traverse_with_bfs()


def getPath(start,finish,parents):
    finish=finish.id
    path=[finish]
    if finish in parents:
        node=parents[finish]
        while(node!=start.id):
            path.append(node)
            node=parents[node]
    else:
        "No Path "
    path.append(start.id)
    return path[::-1]

def test_traverse_withbfs2():
    g=buildGraph()
    start=g.getVertex("fool")
    stop=g.getVertex("sage")
    parents=bfs2(g,start,stop)
    #print(parents.keys())
    path=getPath(start,stop,parents)
    print(path)

test_traverse_withbfs2()