Python資料結構-圖
圖是一種重要的資料結構,它可以代表各種結構和系統,從運輸網路到通訊網路,從細胞核中的蛋白質相互作用到人類線上互動。
圖是由頂點的有窮非空集合和頂點之間邊的集合組成,通常表示為:G(V,E),其中,G表示一個圖,V是圖G中的頂點的集合,E是圖G中邊的集合。如下圖:
下面將以如圖所示的有向圖為例進行說明 Python 中圖結構的表示方法。
鄰接集合
對於圖結構的實現來說,最直觀的方式之一就是使用鄰接列表。基本上就是針對每個節點設定一個鄰接列表,可以使用集合、列表或者字典來實現。第一種是針對每個節點設定一個鄰居集合。
# 將節點的編號賦值給相應的節點,方便操作 a, b, c, d, e, f, g, h = range(8) N = [ {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 ] # 列表中每個集合是每個節點鄰接點集
N(v) 代表 v 的鄰接點集。測試:
>>>b in N[a]# 節點 b 是否是 a 的鄰居節點 True >>>len(N[a])# 節點 a 的出度 5
鄰接列表
與鄰接集合類似,只是針對每個節點設定的是一個包含所有鄰居的列表,而不是集合。
a, b, c, d, e, f, g, h = range(8) N = [ [b, c, d, e, f], [c, e], [d], [e], [f], [c, g, h], [f, h], [f, g] ]
加權鄰接字典
使用字典型別來代替集合或列表來表示鄰接表。在字典型別中,每個鄰居節點都會有一個鍵和一個額外的值,用於表示與其鄰居節點(或出邊)之間的關聯性,如邊的權重。
a, b, c, d, e, f, g, h = range(8) N = [ {b: 2, c: 1, d: 3, e: 9, f: 4},# a {c: 4, e: 3},# b {d: 8},# c {e: 7},# d {f: 5}, # e {c: 2, g: 2, h: 2},# f {f: 1, h: 6},# g {f: 9, g: 8}# h ]
測試:
>>>b in N[a]# b 是否是 a 的鄰居節點 True >>>len(N[f])# 度 3 >>>N[a][b]# 邊(a, b)的權重 2
鄰接集字典
以上圖的表示方法都使用了list型別,其實,也可以使用巢狀的字典結構來實現。
N = {'a':set('bcdef'), 'b':set('ce'), 'c':set('d'), 'd':set('e'), 'e':set('f'), 'f':set('cgh'), 'g':set('fh'), 'h':set('fg') } # 如果省略set()構造器,用鄰接字串表示鍵值,工作方式相當於鄰接列表
當然,字典的值也可以使用列表來表示。測試:
>>>'h' in N['a']# a 是否有到 h 的邊 False >>>len(N['g'])# 節點 g 的度 2
巢狀字典
也可以使用巢狀字典的方式來實現加權圖。
N = {'a':{'b':2, 'c':1, 'd':3, 'e':9, 'f':4}, 'b':{'c':4, 'e':3}, 'c':{'d':8}, 'd':{'e':7}, 'e':{'f':5}, 'f':{'c':2, 'g':2, 'h':2}, 'g':{'f':1, 'h':6}, 'h':{'f':9, 'g':8} }
測試:
>>>'f' in N['e']# e 是否有到 f 的邊 True >>>len(N['e'])# 節點 e 的度 1 >>>N['a']['e']# 邊(a, e)的權重 9
鄰接矩陣
圖的另一種常見表示法就是鄰接矩陣。這種表示的主要不同之處在於,它不再列出每個節點的所有鄰居節點,而是會將每個節點可能的鄰居位置排成一行(也就是一個數組,用於對應圖中每一個節點),然後用某種值(如True或False)來表示相關節點是否為當前節點的鄰居。
a, b, c, d, e, f, g, h = range(8) N =[ [0, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 0, 1], [0, 0, 0, 0, 0, 1, 1, 0], ]
測試:
>>>N[a][b] # a 是否有到 f 的邊 1 >>>sum(N[f]) # 節點 f 的度,不能再用 len 函式 3
注意,鄰接矩陣中:
- 主對角線為自己到自己,為 0
- 行和為出度
- 列和為入度
加權鄰接矩陣
對不存在的邊賦予無限大權值的加權矩陣。
a, b, c, d, e, f, g, h = range(8) inf = float("inf")# 無窮大 W = [ [0,2,1,3,9,4, inf, inf],# a [inf,0,4, inf,3, inf, inf, inf],# b [inf, inf,0,8, inf, inf, inf, inf],# c [inf, inf, inf,0,7, inf, inf, inf],# d [inf, inf, inf, inf,0,5, inf, inf],# e [inf, inf,2, inf, inf,0,2,2],# f [inf, inf, inf, inf, inf,1,0,6],# g [inf, inf, inf, inf, inf,9,8,0]# h ]
測試:
>>>W[a][b] < inf # a 是否有到 b 的邊 True >>>W[c][e] < inf # c 是否有到 e 的邊 False >>>sum(1 for w in W[a] if w < inf) - 1 # 度 5
參考資料:
Hetland M L. Python Algorithms: mastering basic algorithms in the Python Language[M]. Apress, 2014.