1、引入

由 “ 爱 丽 丝 漫 游 奇 境 ” 的 作 者 LewisCarroll在1878年所发明的单词游戏，从一个单词演变到另一个单词， 其中的过程可以经过多个中间单词，要求是相邻两个单词之间差异只能是1个字母，
如FOOL变SAGE：
FOOL >> POOL >> POLL >> POLE >> PALE>> SALE >> SAGE

2、功能分析

在上述问题中，我们的目标是找到最短的单词变换序列
采用图来解决这个问题的步骤如下：

• 将可能的单词之间的演变关系表达为图
• 采用**“广度优先搜索 BFS”**，来搜寻从开始单词
• 到结束单词之间的所有有效路径
• 选择其中最快到达目标单词的路径

（1）构建单词关系图

首先是如何将大量的单词集放到图中，将单词作为顶点的标识Key
如果两个单词之间仅相差1个字母，就在它们之间设一条边，下图是从FOOL到SAGE的词梯解， 所用的图是无向图， 边没有权重，FOOL到SAGE的每条路径都是一个解

单词关系图可以通过不同的算法来构建（以4个字母的单词表为例），首先是将所有单词作为顶点加入图中，再设法建立顶点之间的边，建立边的最直接算法， 是对每个顶点（单词） ， 与其它所有单词进行比较， 如果相差仅1个字母， 则建立一条边，时间复杂度是O(n^2)，对于所有4个字母的5110个单词，需要超过2600万次比较，改进的算法是创建大量的桶， 每个桶可以存放若干单词，桶标记是去掉1个字母，通配符“_”占空的单词，所有匹配标记的单词都放到这个桶里，所有单词就位后，再在同一个桶的单词之间建立边即可。

样例数据文件包含了5,110个4字母单词 （链接: https://pan.baidu.com/s/1nwx_H6xpL5trOtq5e58CsQ 提取码: nb9g）
如果采用邻接矩阵表示这个单词关系图，则需要2,600万个矩阵单元
5,110*5,110= 26,112,100而单词关系图总计有53,286条边，仅仅达到矩阵单元数量的0.2%，所以单词关系图是一个非常稀疏的图，因此采用邻接表来进行图的表示。

def buildGraph(wordFile):
    d = {}
    g = Graph()    
    wfile = open(wordFile,'r')
    # create buckets 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)
    print(d)
    return g

（2）广度优先搜索寻找最短序列

在单词关系图建立完成以后， 需要继续在图中寻找词梯问题的最短序列，需要用到**“广度优先搜索Breadth First Search”**算法对单词关系图进行搜索，BFS是搜索图的最简单算法之一， 也是其它一些重要的图算法的基础。

• 给定图G， 以及开始搜索的起始顶点s
• BFS搜索所有从s可到达顶点的边
• 而且在达到更远的距离k+1的顶点之前， BFS会找到全部距离为k的顶点
• 可以想象为以s为根，构建一棵树的过程，从顶部向下逐步增加层次 广度优先搜索能保证在增加层次之前，添加了所有兄弟节点到树中

为了跟踪顶点的加入过程， 并避免重复顶点， 要为顶点增加3个属性

• 距离distance：从起始顶点到此顶点路径长度
• 前驱顶点predecessor：可反向追溯到起点
• 颜色color：标识了此顶点是尚未发现（白色）、已经发现（灰色）、还是已经完成探索（黑色）

还需要用一个队列Queue来对已发现的顶点进行排列，决定下一个要探索的顶点（队首顶点）
从起始顶点s开始， 作为刚发现的顶点，标注为灰色， 距离为0， 前驱为None，加入队列， 接下来是个循环迭代过程：

• 从队首取出一个顶点作为当前顶点；
• 遍历当前顶点的邻接顶点，如果是尚未发现的白色顶点，则将其颜色改为灰色（已发现），距离增加1，前驱顶点为当前顶点，加入到队列中
• 遍历完成后，将当前顶点设置为黑色（已探索过），循环回到步骤1的队首取当前顶点

下面构造以下单词图的图结构

（3）回溯输出结果

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

3、代码实现

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)
class Graph:
    # 图结构初始化
    def __init__(self):
        self.vertices = {}
        self.numVertices = 0
    # 增加节点
    def addVertex(self,key):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.vertices[key] = newVertex
        return newVertex
    # 获取节点
    def getVertex(self,n):
        if n in self.vertices:
            return self.vertices[n]
        else:
            return None
    # 特殊方法 in
    def __contains__(self,n):
        return n in self.vertices
    # 添加边
    def addEdge(self,f,t,cost=0):
            if f not in self.vertices:
                nv = self.addVertex(f)
            if t not in self.vertices:
                nv = self.addVertex(t)
            self.vertices[f].addNeighbor(self.vertices[t],cost)
    # 获取所有顶点的key值
    def getVertices(self):
        return list(self.vertices.keys())
    # 特殊方法 迭代器
    def __iter__(self):
        return iter(self.vertices.values())
                
class Vertex:
    # 顶点初始化
    def __init__(self,num):
        self.id = num
        self.connectedTo = {}
        self.color = 'white'        #颜色
        self.dist = sys.maxsize     #距离
        self.pred = None            #前驱节点
        self.disc = 0               #开始时间
        self.fin = 0                #结束时间
    # 比较大小
    # def __lt__(self,o):
    #     return self.id < o.id
    # 添加邻边节点
    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr] = weight
    # 设置颜色
    def setColor(self,color):
        self.color = color
    # 设置距离
    def setDistance(self,d):
        self.dist = d
    # 设置前驱
    def setPred(self,p):
        self.pred = p
    # 设置发现时间
    def setDiscovery(self,dtime):
        self.disc = dtime
    # 设置结束时间
    def setFinish(self,ftime):
        self.fin = ftime
    # 获取结束时间
    def getFinish(self):
        return self.fin
    # 获取发现时间
    def getDiscovery(self):
        return self.disc
    # 获取前驱
    def getPred(self):
        return self.pred
    # 获取距离
    def getDistance(self):
        return self.dist
    # 获取颜色
    def getColor(self):
        return self.color
    # 获取连接边
    def getConnections(self):
        return self.connectedTo.keys()
    # 获取与某个节点间的权重值
    def getWeight(self,nbr):
        return self.connectedTo[nbr]
    # 特殊方法 print
    def __str__(self):
        return str(self.id) + ":color " + self.color + ":disc " + str(self.disc) + ":fin " + str(self.fin) + ":dist " + str(self.dist) + ":pred \n\t[" + str(self.pred)+ "]\n"
    # 获取Id
    def getId(self):
        return self.id
        
def buildGraph(wordFile):
    d = {}
    g = Graph()    
    wfile = open(wordFile,'r')
    # create buckets 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)
    print(d)
    return g
    

def bfs(g,start):
  start.setDistance(0)
  start.setPred(None)
  vertQueue = Queue()
  vertQueue.enqueue(start)
  while (vertQueue.size() > 0):
    currentVert = vertQueue.dequeue()
    for nbr in currentVert.getConnections():
      if (nbr.getColor() == 'white'):
        nbr.setColor('gray')
        nbr.setDistance(currentVert.getDistance() + 1)
        nbr.setPred(currentVert)
        vertQueue.enqueue(nbr)
    currentVert.setColor('black') 
    
    
def traverse(y):
    x = y
    while (x.getPred()):
        print(x.getId())
        x = x.getPred()
    print(x.getId())

4、测试代码及结果

wordgraph = buildGraph("fourletterwords.txt")

bfs(wordgraph, wordgraph.getVertex('FOOL'))

traverse(wordgraph.getVertex('SAGE'))