|
圖結(jié)構(gòu)： 非常強大的結(jié)構(gòu)化思維（或數(shù)學(xué)）模型。如果您能用圖的處理方式來規(guī)范化某個問題，即使這個問題本身看上去并不像個圖問題，也能使您離解決問題更進一步。 在眾多圖算法中，我們常會用到一種非常實用的思維模型--遍歷（traversal）:對圖中所有節(jié)點的探索及訪問操作。
圖的一些相關(guān)概念： 簡單圖（Simple graph）：無環(huán)并且無平行邊的圖. 路（path）：內(nèi)部點互不相同的鏈。 如果無向圖G中每一對不同的頂點x和y都有一條路，（即W（G）=1，連通分支數(shù)）則稱G是連通圖，反之稱為非連通圖。 兩端點相同的路（即閉路）稱為圈（cycle）。 樹（tree）是無圈連通無向圖。樹中度數(shù)為1的結(jié)點稱為樹的葉結(jié)點。樹中度數(shù)大于1的結(jié)點稱為樹的分支節(jié)點或內(nèi)部結(jié)點。 不相交的若干樹稱為森林（forest）,即森林的每個連通分支是樹。 定理1：T是樹<=>T中無環(huán)，且任何不同兩頂點間有且僅有一條路。 定理2：T是樹<=>T連通且|e|=n-1，|e|為T的邊數(shù)，n為T的頂點數(shù)。 由根到某一頂點v的有向路的長度，稱為頂點v的層數(shù)（level）。根樹的高度就是頂點層數(shù)的最大值。
深度優(yōu)先搜索： 求連通簡單圖G的一棵生成樹的許多方法中，深度優(yōu)先搜索（depth first search）是一個十分重要的算法。 基本思想： 任意選擇圖G的一個頂點V0作為根，通過相繼地添加邊來形成在頂點V0開始的路，其中每條新邊都與路上的最后一個頂點以及不在路上的一個頂點相關(guān)聯(lián)。 繼續(xù)盡可能多地添加邊到這條路。若這條路經(jīng)過圖G的所有頂點，則這條路即為G的一棵生成樹； 若這條路沒有經(jīng)過G的所有頂點，不妨設(shè)形成這條路的頂點順序V0,V1,......,Vn。則返回到路里的次最后頂點V(n-1). 若有可能，則形成在頂點v(n-1)開始的經(jīng)過的還沒有放過的頂點的路； 否則，返回到路里的頂點v(n-2)。 然后再試。重復(fù)這個過程，在所訪問過的最后一個頂點開始，在路上次返回的頂點，只要有可能就形成新的路，直到不能添加更多的邊為止。 深度優(yōu)先搜索也稱為回溯（back tracking） 栗子： 用深度優(yōu)先搜索來找出圖3-9所示圖G的生成樹，任意地從頂點d開始，生成步驟顯示在圖3-10。
廣度優(yōu)先搜索： 可用廣度優(yōu)先搜索（breadth first search）來產(chǎn)生連通簡單圖的生成樹。 基本思想： 從圖的頂點中任意第選擇一個根，然后添加與這個頂點相關(guān)聯(lián)的所有邊，在這個階段添加的新頂點成為生成樹里1層上的頂點，任意地排序它們。 下一步，按照順序訪問1層上的每一個頂點，只要不產(chǎn)生回路，就添加與這個頂點相關(guān)聯(lián)的每個邊。這樣就產(chǎn)生了樹里2的上的頂點。遵循同樣的原則繼續(xù)下去，經(jīng)有限步驟就產(chǎn)生了生成樹。 栗子： 用廣度優(yōu)先搜索找出圖3-9所示圖G的生成樹，選擇頂點f作為根：
兩種著名的基本遍歷策略： 深度優(yōu)先搜索（depth-first search） 廣度優(yōu)先搜索（breadth-first search）
找出圖的連通分量： 如果一個圖中的任何一個節(jié)點都有一條路徑可以到達其他各個節(jié)點，那么它就是連通的。 連通分量：目標圖中最大（且獨立）的連通子圖。 從圖中的某個部分開始，逐步擴大其連通子圖的確認范圍，直至它再也無法向外連通為止。  def walk(G,s,S=set()): P,Q=dict(),set() P[s]=None # s節(jié)點沒有前任節(jié)點 Q.add(s) # 從s開始搜索 while Q: u=Q.pop() for v in G[u].difference(P,S): # 得到新節(jié)點 Q.add(v) P[v]=u # 記錄前任節(jié)點 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 yurefxw, # 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)先搜索的拓撲排序 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 eavluvn, # 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
強連通分量 如果有向圖的任何一對結(jié)點間是相互可達的，則稱這個有向圖是強連通的
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'}]
|
|
|
來自： highoo > 《數(shù)據(jù)分析》
