圖結構：
非常強大的結構化思維（或數學）模型。如果您能用圖的處理方式來規範化某個問題，即使這個問題本身看上去并不像個圖問題，也能使您離解決問題更進一步。
在衆多圖算法中，我們常會用到一種非常實用的思維模型--周遊（traversal）:對圖中所有節點的探索及通路操作。
圖的一些相關概念：
簡單圖（Simple graph）：無環并且無平行邊的圖.
路（path）：内部點互不相同的鍊。
如果無向圖G中每一對不同的頂點x和y都有一條路，（即W（G）=1，連通分支數）則稱G是連通圖，反之稱為非連通圖。
兩端點相同的路（即閉路）稱為圈（cycle）。
樹（tree）是無圈連通無向圖。樹中度數為1的結點稱為樹的葉結點。樹中度數大于1的結點稱為樹的分支節點或内部結點。
不相交的若幹樹稱為森林（forest）,即森林的每個連通分支是樹。
定理1：T是樹<=>T中無環，且任何不同兩頂點間有且僅有一條路。
定理2：T是樹<=>T連通且|e|=n-1，|e|為T的邊數，n為T的頂點數。
由根到某一頂點v的有向路的長度，稱為頂點v的層數（level）。根樹的高度就是頂點層數的最大值。
深度優先搜尋：
求連通簡單圖G的一棵生成樹的許多方法中，深度優先搜尋（depth first search）是一個十分重要的算法。
基本思想：
任意選擇圖G的一個頂點V0作為根，通過相繼地添加邊來形成在頂點V0開始的路，其中每條新邊都與路上的最後一個頂點以及不在路上的一個頂點相關聯。
繼續盡可能多地添加邊到這條路。若這條路經過圖G的所有頂點，則這條路即為G的一棵生成樹；
若這條路沒有經過G的所有頂點，不妨設形成這條路的頂點順序V0,V1,......,Vn。則傳回到路裡的次最後頂點V(n-1).
若有可能，則形成在頂點v(n-1)開始的經過的還沒有放過的頂點的路；
否則，傳回到路裡的頂點v(n-2)。
然後再試。重複這個過程，在所通路過的最後一個頂點開始，在路上次傳回的頂點，隻要有可能就形成新的路，直到不能添加更多的邊為止。
深度優先搜尋也稱為回溯（back tracking）
栗子：
用深度優先搜尋來找出圖3-9所示圖G的生成樹，任意地從頂點d開始，生成步驟顯示在圖3-10。
廣度優先搜尋：
可用廣度優先搜尋（breadth first search）來産生連通簡單圖的生成樹。
基本思想：
從圖的頂點中任意第選擇一個根，然後添加與這個頂點相關聯的所有邊，在這個階段添加的新頂點成為生成樹裡1層上的頂點，任意地排序它們。
下一步，按照順序通路1層上的每一個頂點，隻要不産生回路，就添加與這個頂點相關聯的每個邊。這樣就産生了樹裡2的上的頂點。遵循同樣的原則繼續下去，經有限步驟就産生了生成樹。
栗子：
用廣度優先搜尋找出圖3-9所示圖G的生成樹，選擇頂點f作為根：
兩種著名的基本周遊政策：
深度優先搜尋（depth-first search）
廣度優先搜尋（breadth-first search）
找出圖的連通分量：
如果一個圖中的任何一個節點都有一條路徑可以到達其他各個節點，那麼它就是連通的。
連通分量：目标圖中最大（且獨立）的連通子圖。
從圖中的某個部分開始，逐漸擴大其連通子圖的确認範圍，直至它再也無法向外連通為止。
def walk(G,s,S=set()):
P,Q=dict(),set()
P[s]=None # s節點沒有前任節點
Q.add(s) # 從s開始搜尋
while Q:
u=Q.pop()
for v in G[u].difference(P,S): # 得到新節點
Q.add(v)
P[v]=u # 記錄前任節點
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) 深度優先搜尋：
遞歸版的深度優先搜尋 :
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) 疊代版的深度優先搜尋 :
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
{d}, # 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] 通用性的圖周遊函數
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)) 基于深度優先搜尋的拓撲排序
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
if __name__=="__main__":
a, b, c, d, e, f, g, h, i = range(9)
G = {
'a': set('bf'),
'b': set('cdf'),
'c': set('d'),
'd': set('ef'),
'e': set('f'),
'f': set('')
}
res = dfs_topsort(G) 疊代深度的深度優先搜尋
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
{d}, # 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] 廣度優先搜尋
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 強連通分量
如果有向圖的任何一對結點間是互相可達的，則稱這個有向圖是強連通的
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'}]