|
圖結(jié)構(gòu)： 非常強(qiáng)大的結(jié)構(gòu)化思維（或數(shù)學(xué)）模型。如果您能用圖的處理方式來(lái)規(guī)范化某個(gè)問(wèn)題，即使這個(gè)問(wèn)題本身看上去并不像個(gè)圖問(wèn)題，也能使您離解決問(wèn)題更進(jìn)一步。 在眾多圖算法中，我們常會(huì)用到一種非常實(shí)用的思維模型--遍歷（traversal）:對(duì)圖中所有節(jié)點(diǎn)的探索及訪問(wèn)操作。
圖的一些相關(guān)概念： 簡(jiǎn)單圖（Simple graph）：無(wú)環(huán)并且無(wú)平行邊的圖. 路（path）：內(nèi)部點(diǎn)互不相同的鏈。 如果無(wú)向圖G中每一對(duì)不同的頂點(diǎn)x和y都有一條路，（即W（G）=1，連通分支數(shù)）則稱(chēng)G是連通圖，反之稱(chēng)為非連通圖。 兩端點(diǎn)相同的路（即閉路）稱(chēng)為圈（cycle）。 樹(shù)（tree）是無(wú)圈連通無(wú)向圖。樹(shù)中度數(shù)為1的結(jié)點(diǎn)稱(chēng)為樹(shù)的葉結(jié)點(diǎn)。樹(shù)中度數(shù)大于1的結(jié)點(diǎn)稱(chēng)為樹(shù)的分支節(jié)點(diǎn)或內(nèi)部結(jié)點(diǎn)。 不相交的若干樹(shù)稱(chēng)為森林（forest）,即森林的每個(gè)連通分支是樹(shù)。 定理1：T是樹(shù)<=>T中無(wú)環(huán)，且任何不同兩頂點(diǎn)間有且僅有一條路。 定理2：T是樹(shù)<=>T連通且|e|=n-1，|e|為T(mén)的邊數(shù)，n為T(mén)的頂點(diǎn)數(shù)。 由根到某一頂點(diǎn)v的有向路的長(zhǎng)度，稱(chēng)為頂點(diǎn)v的層數(shù)（level）。根樹(shù)的高度就是頂點(diǎn)層數(shù)的最大值。
深度優(yōu)先搜索： 求連通簡(jiǎn)單圖G的一棵生成樹(shù)的許多方法中，深度優(yōu)先搜索（depth first search）是一個(gè)十分重要的算法。 基本思想： 任意選擇圖G的一個(gè)頂點(diǎn)V0作為根，通過(guò)相繼地添加邊來(lái)形成在頂點(diǎn)V0開(kāi)始的路，其中每條新邊都與路上的最后一個(gè)頂點(diǎn)以及不在路上的一個(gè)頂點(diǎn)相關(guān)聯(lián)。 繼續(xù)盡可能多地添加邊到這條路。若這條路經(jīng)過(guò)圖G的所有頂點(diǎn)，則這條路即為G的一棵生成樹(shù)； 若這條路沒(méi)有經(jīng)過(guò)G的所有頂點(diǎn)，不妨設(shè)形成這條路的頂點(diǎn)順序V0,V1,......,Vn。則返回到路里的次最后頂點(diǎn)V(n-1). 若有可能，則形成在頂點(diǎn)v(n-1)開(kāi)始的經(jīng)過(guò)的還沒(méi)有放過(guò)的頂點(diǎn)的路； 否則，返回到路里的頂點(diǎn)v(n-2)。 然后再試。重復(fù)這個(gè)過(guò)程，在所訪問(wèn)過(guò)的最后一個(gè)頂點(diǎn)開(kāi)始，在路上次返回的頂點(diǎn)，只要有可能就形成新的路，直到不能添加更多的邊為止。 深度優(yōu)先搜索也稱(chēng)為回溯（back tracking） 栗子： 用深度優(yōu)先搜索來(lái)找出圖3-9所示圖G的生成樹(shù)，任意地從頂點(diǎn)d開(kāi)始，生成步驟顯示在圖3-10。
廣度優(yōu)先搜索： 可用廣度優(yōu)先搜索（breadth first search）來(lái)產(chǎn)生連通簡(jiǎn)單圖的生成樹(shù)。 基本思想： 從圖的頂點(diǎn)中任意第選擇一個(gè)根，然后添加與這個(gè)頂點(diǎn)相關(guān)聯(lián)的所有邊，在這個(gè)階段添加的新頂點(diǎn)成為生成樹(shù)里1層上的頂點(diǎn)，任意地排序它們。 下一步，按照順序訪問(wèn)1層上的每一個(gè)頂點(diǎn)，只要不產(chǎn)生回路，就添加與這個(gè)頂點(diǎn)相關(guān)聯(lián)的每個(gè)邊。這樣就產(chǎn)生了樹(shù)里2的上的頂點(diǎn)。遵循同樣的原則繼續(xù)下去，經(jīng)有限步驟就產(chǎn)生了生成樹(shù)。 栗子： 用廣度優(yōu)先搜索找出圖3-9所示圖G的生成樹(shù)，選擇頂點(diǎn)f作為根：
兩種著名的基本遍歷策略： 深度優(yōu)先搜索（depth-first search） 廣度優(yōu)先搜索（breadth-first search）
找出圖的連通分量： 如果一個(gè)圖中的任何一個(gè)節(jié)點(diǎn)都有一條路徑可以到達(dá)其他各個(gè)節(jié)點(diǎn)，那么它就是連通的。 連通分量：目標(biāo)圖中最大（且獨(dú)立）的連通子圖。 從圖中的某個(gè)部分開(kāi)始，逐步擴(kuò)大其連通子圖的確認(rèn)范圍，直至它再也無(wú)法向外連通為止。  def walk(G,s,S=set()): P,Q=dict(),set() P[s]=None # s節(jié)點(diǎn)沒(méi)有前任節(jié)點(diǎn) Q.add(s) # 從s開(kāi)始搜索 while Q: u=Q.pop() for v in G[u].difference(P,S): # 得到新節(jié)點(diǎn) Q.add(v) P[v]=u # 記錄前任節(jié)點(diǎn) return P def components(G): comp = [] seen = set() for u in range(9): if u in seen: continue C = walk(G, u) seen.update(C) comp.append(C) return comp if __name__ == "__main__": a, b, c, d, e, f, g, h, i= range(9) N = [ {b, c, d}, # a {a, d}, # b {a,d}, # c {a,c,d}, # d {g,f}, # e {e,g}, # f {e,f}, # g {i}, # h {h} # i ] comp = components(N) print(comp)
深度優(yōu)先搜索： 遞歸版的深度優(yōu)先搜索 : def rec_dfs(G,s,S=None): if S is None:S = set() S.add(s) for u in G[s]: if u in S:coontinue rec_dfs(G,u,S) 迭代版的深度優(yōu)先搜索 : def iter_dfs(G,s): S,Q=set(),[] Q.append(s) while Q: u = Q.pop() if u in S:continue S.add(u) Q.extend(G[u]) yield u if __name__ == "__main__": a, b, c, d, e, f, g, h, i = range(9) G = [{b, c, d, e, f}, # a {c, e}, # b opkdopnojk, # c {e}, # d {f}, # e {c, g, h}, # f {f, h}, # g {f, g} # h ] print(list(iter_dfs(G,a))) # [0, 5, 7, 6, 2, 3, 4, 1] 通用性的圖遍歷函數(shù)  def traverse(G,s,qtype=set()): S,Q=set(),qtype() Q.add(s) while Q: u=Q.pop() if u in S:continue S.add(u) for v in G[u]: Q.add(v) yield u class stack(list): add=list.append g=list(traverse(G,0,stack))
基于深度優(yōu)先搜索的拓?fù)渑判?/span> def dfs_topsort(G): S,res=set(),[]
迭代深度的深度優(yōu)先搜索 def iddfs(G,s): yielded=set() def recurse(G,s,d,S=None): if s not in yielded: yield s yielded.add(s) if d==0:return if S is None:S=set() S.add(s) for u in G[s]: if u in S:continue for v in recurse(G,u,d-1,S): yield v n=len(G) for d in range(n): if len(yielded)==n:break for u in recurse(G,s,d): yield u if __name__=="__main__": a, b, c, d, e, f, g, h, i= range(9) N = [ {b, c, d}, # a {a, d}, # b {a,d}, # c {a,b,c}, # d {g,f}, # e {e,g}, # f {e,f}, # g {i}, # h {h} # i ] G = [{b,c,d,e,f},#a {c,e}, # b opkdopnojk, # c {e}, # d {f}, # e {c,g,h}, # f {f,h}, # g {f,g} # h ] p=list(iddfs(G,0)) # [0, 1, 2, 3, 4, 5, 6, 7] m=list(iddfs(N,0)) # [0, 1, 2, 3]
廣度優(yōu)先搜索 import collections def bfs(G,s): P,Q={s:None},collections.deque([s]) while Q: u=Q.popleft() for v in G[u]: if v in P:continue P[v]=u Q.append(v) return P
強(qiáng)連通分量 如果有向圖的任何一對(duì)結(jié)點(diǎn)間是相互可達(dá)的，則稱(chēng)這個(gè)有向圖是強(qiáng)連通的
def tr(G): GT={} for u in G:GT[u]=set() for u in G: for v in G[u]: GT[v].add(u) return GT def scc(G): GT=tr(G) sccs,seen=[],set() for u in dfs_topsort(G): if u in seen:continue C=walk(GT,u,seen) seen.update(C) sccs.append(C) return sccs def dfs_topsort(G): S,res=set(),[] def recurse(u): if u in S:return S.add(u) for v in G[u]: recurse(v) res.append(u) for u in G: recurse(u) res.reverse() return res def walk(G,s,S=set()): P,Q=dict(),set() P[s]=None Q.add(s) while Q: u=Q.pop() print("u: ",u) print("S:",S) for v in G[u].difference(P,S): Q.add(v) P[v]=u return P if __name__=="__main__": a, b, c, d, e, f, g, h, i= range(9) G={ 'a':set('bc'), 'b':set('edi'), 'c':set('d'), 'd':set('ah'), 'e':set('f'), 'f':set('g'), 'g':set('eh'), 'h':set('i'), 'i':set('h') } sccs=scc(G) # [{'a': None, 'd': 'a', 'c': 'd', 'b': 'd'}, {'e': None, 'g': 'e', 'f': 'g'}, {'h': None, 'i': 'h'}]
|
|
|
來(lái)自： highoo > 《數(shù)據(jù)分析》
