學(xué)習(xí)目標(biāo)：

    1.了解圖是什么，如何構(gòu)建

    2.使用圖來(lái)解決問(wèn)題

一 、常用術(shù)語(yǔ)

頂點(diǎn)：頂點(diǎn)是圖的基本部分，我們也可稱為鍵。

邊：邊可以連接兩個(gè)頂點(diǎn)，以表明他們之間的關(guān)系?？梢允请p向也可以是單向。如果都是單向的，我們稱圖為有向圖。

權(quán)重：邊可被加權(quán)，表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的成本。

路徑：圖中的路徑是由邊連接的頂點(diǎn)序列。

循環(huán)：有向圖中的循環(huán)是在同一頂點(diǎn)開(kāi)始和結(jié)束的路徑。

二、實(shí)現(xiàn)方式

實(shí)現(xiàn)圖的最簡(jiǎn)單的方法：一是二維矩陣。每個(gè)行和列表示圖中的頂點(diǎn)。優(yōu)點(diǎn)：實(shí)現(xiàn)方式簡(jiǎn)單。二、鄰接表。在鄰接表實(shí)現(xiàn)中，我們保存Graph對(duì)象中的所有頂點(diǎn)的主列表，然后圖中的每個(gè)頂點(diǎn)對(duì)象維護(hù)連接到的其他頂點(diǎn)的列表。

#創(chuàng)建一個(gè)頂點(diǎn)類
class Vertex(object):
    def __init__(self,key):
        self.id=key
        self.connectedTo={} #利用字典來(lái)追蹤它連接的頂點(diǎn)和每個(gè)邊的權(quán)重。
    #添加頂點(diǎn)
    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr]=weight
    #返回鄰接表中的所有頂點(diǎn)
    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id
    #返回從這個(gè)頂點(diǎn)到參數(shù)傳遞的頂點(diǎn)的權(quán)重
    def getWeight(self,nbr):
        return self.connectedTo[nbr]

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


#創(chuàng)建Graph類,將頂點(diǎn)名稱映射到頂點(diǎn)對(duì)象的字典
class Graph(object):
    def __init__(self):
        self.vertList={}
        self.numVertices=0
    #
    def addVertex(self,key):
        self.numVertices=self.numVertices+1
        newVertex=Vertex(key)#頂點(diǎn)
        self.vertList[key]=newVertex
        return newVertex
    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 addEdage(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())



if __name__=="__main__":
    g=Graph()
    #添加頂點(diǎn)
    for i in range(6):
        g.addVertex(i)
    #添加邊
    g.addEdage(0,1,5)
    g.addEdage(0,5,2)
    g.addEdage(1, 2, 4)
    g.addEdage(2,3,9)
    g.addEdage(3,4, 7)
    g.addEdage(3,5,2)
    g.addEdage(4,0,1)
    g.addEdage(5,4,8)
    g.addEdage(5,2,1)
    for v in g:
        for w in v.getConnections():
            print("(%s,%s)" %(v.getId(),w.getId()))

具體問(wèn)題---字梯的問(wèn)題
字梯的問(wèn)題：是指將單詞“FOOL”轉(zhuǎn)換成單詞”SAGE”。在字梯中你通過(guò)改變一個(gè)字母逐漸發(fā)生變化。每一步，你必須將一個(gè)將一個(gè)字換成另一個(gè)字。

FOOL
POOL
POLL
POLE
PALE
SALE
SAGE

怎樣利用圖來(lái)解決這個(gè)問(wèn)題。主要步驟：
（1）將字之間的關(guān)系表示為圖
（2）使用廣度優(yōu)先搜索的圖算法來(lái)找到從起始到結(jié)束字的游俠路徑
先看廣度優(yōu)先：
（1）頂點(diǎn)v入隊(duì)列。
（2）當(dāng)隊(duì)列非空時(shí)則繼續(xù)執(zhí)行，否則算法結(jié)束。
（3）出隊(duì)列取得隊(duì)頭頂點(diǎn)v；訪問(wèn)頂點(diǎn)v并標(biāo)記頂點(diǎn)v已被訪問(wèn)。
（4）查找頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)col。
（5）若v的鄰接頂點(diǎn)col未被訪問(wèn)過(guò)的，則col入隊(duì)列。
（6）繼續(xù)查找頂點(diǎn)v的另一個(gè)新的鄰接頂點(diǎn)col，轉(zhuǎn)到步驟（5）。直到頂點(diǎn)v的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)處理完。轉(zhuǎn)到步驟（2）。

def bfs(self,start):
    queue = [start] #創(chuàng)建隊(duì)列
    result = []
    visited = [False for i in range(self.v)] #標(biāo)記是否被訪問(wèn)
    while queue: #隊(duì)列不為空
        now = queue.pop(0) #當(dāng)前節(jié)點(diǎn)
        if not visited[now]:#沒(méi)有被訪問(wèn)時(shí)
            visited[now] = True
            result.append(now)
        for i in range(self.v):
            if self.graph[now][i]!= 0 and  visited[i] is False:
                queue.append(i)
    return result

具體問(wèn)題---騎士之旅（深度優(yōu)先算法）
（1）訪問(wèn)初始頂點(diǎn)v并標(biāo)記頂點(diǎn)v已訪問(wèn)。
（2）查找頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)w。
（3）若頂點(diǎn)v的鄰接頂點(diǎn)w存在，則繼續(xù)執(zhí)行；否則回溯到v，再找v的另外一個(gè)未訪問(wèn)過(guò)的鄰接點(diǎn)。
（4）若頂點(diǎn)w尚未被訪問(wèn)，則訪問(wèn)頂點(diǎn)w并標(biāo)記頂點(diǎn)w為已訪問(wèn)。
（5）繼續(xù)查找頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)wi，如果v取值wi轉(zhuǎn)到步驟（3）。直到連通圖中所有頂點(diǎn)全部訪問(wèn)過(guò)為止。