問(wèn)題：找到最短的單詞變換序列

方法：

①將可能單詞之間的演變表示為圖 ，將單詞放入圖中，如果單詞之間差一個(gè)字母，就在之間設(shè)一條邊。該圖是無(wú)向圖，沒(méi)有權(quán)重。

image.png

由于建立圖需要兩兩字符串比較，時(shí)間復(fù)雜度為O(N^2)。通過(guò)設(shè)立桶，每個(gè)桶的包括去掉一個(gè)字符的所有字符串：

image.png

時(shí)間復(fù)雜度，最多為O(V^2)

②采用廣度優(yōu)先搜索BFS，搜尋開(kāi)始至結(jié)束單詞的所有有限路徑
從起始頂點(diǎn)開(kāi)始一級(jí)級(jí)探索，賦予頂點(diǎn)三個(gè)屬性

1. 距離（表示與起始頂點(diǎn)的距離）
2. 前驅(qū)頂點(diǎn)（可反向追溯頂點(diǎn)）
3. 顏色（表明是否已經(jīng)探索到）
   4 用一個(gè)隊(duì)列來(lái)記錄需要探索的頂點(diǎn)，隊(duì)首表示下一個(gè)要探索的頂點(diǎn)
   時(shí)間復(fù)雜度，while循環(huán)時(shí)間復(fù)雜度最多為O(V), 里面嵌套的for循環(huán)，由于每個(gè)頂點(diǎn)邊最多檢查一次，為O(E)
   整體時(shí)間復(fù)雜度為O(V+E)

③選擇最快到達(dá)目標(biāo)詞匯的路徑
從目標(biāo)詞匯，回溯至起始詞匯
回溯算法時(shí)間復(fù)雜度為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)
    # 設(shè)立前驅(qū)頂點(diǎn)
    start.setPred(None)
    # 設(shè)立隊(duì)列，儲(chǔ)存探索頂點(diǎn)
    vertQueue = Queue()
    # 入隊(duì)第一個(gè)頂點(diǎn)
    vertQueue.enqueue(start)
    while vertQueue.size() > 0:
        currentVert = vertQueue.dequeue()
        for nbr in currentVert.getConnections():
            if nbr.getColor() == 'white': # 看是否探索過(guò)
                nbr.setColor('grey')
                nbr.setDistance(currentVert.getDistance() + 1)
                nbr.setPred(currentVert)
                vertQueue.enqueue(nbr)
        #探索完畢，變黑，循環(huán)換下一個(gè)頂點(diǎn)
        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'))