图的应用1——词梯问题

问题：找到最短的单词变换序列

方法：

①将可能单词之间的演变表示为图 ，将单词放入图中，如果单词之间差一个字母，就在之间设一条边。该图是无向图，没有权重。

image.png

由于建立图需要两两字符串比较，时间复杂度为O(N^2)。通过设立桶，每个桶的包括去掉一个字符的所有字符串：

image.png

时间复杂度，最多为O(V^2)

②采用广度优先搜索BFS，搜寻开始至结束单词的所有有限路径
从起始顶点开始一级级探索，赋予顶点三个属性

1. 距离（表示与起始顶点的距离）
2. 前驱顶点（可反向追溯顶点）
3. 颜色（表明是否已经探索到）
   4 用一个队列来记录需要探索的顶点，队首表示下一个要探索的顶点
   时间复杂度，while循环时间复杂度最多为O(V), 里面嵌套的for循环，由于每个顶点边最多检查一次，为O(E)
   整体时间复杂度为O(V+E)

③选择最快到达目标词汇的路径
从目标词汇，回溯至起始词汇
回溯算法时间复杂度为O(V)

代码如下：

from eleventh Graph code import Graph

# 将词纳入图中
def buildGraph(wordFile):
    d = {}
    g = Graph()
    wfile = open(wordFile, 'r')
    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]

    # 在单词之间加边
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1,word2)

    return g

# bfs算法
def bfs(g, start):
    # 距离初始化1
    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('grey')
                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())


wordgraph = buildGraph('fourletterwords.txt')
bfs(wordgraph, wordgraph.getVertex('FOOL'))
traverse(wordgraph.getVertex('SAGE'))