圖（一）：圖的概念與基本操作
引言
前文介紹的樹中，元素的關係是一對多，本章介紹一種多對多的數據結構——圖。
圖的定義
一個圖是一個二元組G=(V,E)，其中：
- V是非空有窮的頂點集合；
- E是定點偶對(邊)的集合，E是V×V的子集
- V的中的頂點稱為圖G的頂點，E中的邊稱為圖G的邊
圖示：
上圖被稱為有向圖，有向圖的邊有方向，是頂點的有序對；相對地，無向圖的邊沒有方向，是頂點的無序對。
圖的基本概念和性質
**完全圖：**任意兩個頂點之間都有邊的圖稱為完全圖，其性質如下：
- 有n個頂點的無向完全圖有n×(n-1)/2條邊
- 有n個頂點的有向完全圖有n×(n-1)條邊
**度：**一個頂點的度就是與它鄰接的邊的數目。度還分為出度和入度，出度指的是該頂點指向多少個頂點，入度指的是有多少個頂點指向該頂點。
**路徑：**如果一個頂點能夠到達另一個頂點，那麼這兩個頂點之間的邊的組合稱為路徑。路徑的性質如下：
- 路徑長度=邊的總數
- 環指的是起點和終點相同的路徑
- 如果一個環除起點和終點外其他頂點都不相同，則稱為簡單環
- 如果一條路徑中不存在環，則稱為簡單路徑
**有根圖：**如果在有向圖G里存在一個頂點v，從頂點v到圖G中其他每個頂點都有路徑，則稱呈圖G為有根圖，稱v為圖的一個根。
連通圖：
- 連通：如果一個頂點能夠到達另外一個頂點，則稱它們是連通的
- 連通無向圖：無向圖中如果任意兩個結點都能連通，則稱該圖為連通無向圖
- 強連通有向圖：無向圖中如果任意兩個結點都能相互連通，則稱該圖為強連通有向圖
- 最小連通圖：即去掉任何一條邊，該圖都無法成為連通圖。此外，最小連通無向圖的邊為n-1(頂點有n個)
- 最小有根圖：去掉任何一條邊都無法稱為有根圖，其邊數為n-1(頂點為n)
**帶權圖：**如果圖G的每條邊都被賦予權值，則稱G為一個帶權圖。此外，帶權的連通無向圖也被稱為網絡。
圖的基本操作
圖的操作較多，主要有以下幾種：
- 創建一個圖
- 判斷圖是否為空
- 獲得這個圖的頂點個數
- 獲得這個圖的邊數
- 獲得這個圖的頂點集合
- 獲得這個圖的邊集合
- 向圖中新增一個頂點
- 將從v1到v2的邊加入這個圖
- 獲得v1到v2邊的信息
- 取得從v出發的所有邊
- 檢查v的度
Python實現
圖有以下兩種常用的表示方法：
- 鄰接矩陣表示法，缺點是鄰接矩陣較為稀疏，存在很多無用信息，浪費空間
- 鄰接表表示法，對鄰接矩陣表示法的空間優化
鄰接矩陣表示法實現
class Graph_mat:
def __init__(self, mat, unconn=0):
'''
Parameters
----------
mat : matrix
圖的鄰接矩陣.
uncon : float、string、int, etc.
主要用於表示無關聯時的數值. The default is 0.
Returns
-------
None.
'''
vnum = len(mat) # 頂點數
for x in mat:
if len(x) != vnum:
raise ValueError('mat必須是一個標準的鄰接矩陣！')
self.mat_ = [mat[i][:] for i in range(vnum)] # 拷貝mat
self.unconn_ = unconn
self.vnum_ = vnum
# 獲得頂點的數目
def get_v_count(self):
return self.vnum_
# 判斷頂點下標是否越界
def vertex_invalid(self, v):
return v < 0 or v >= self.vnum_
# 加入頂點
def add_vertex(self, val):
self.mat_.append([self.unconn_ for _ in range(self.vnum_)])
self.vnum_ += 1
for x in self.mat_:
x.append(self.unconn_)
self.mat_[self.vnum_-1][self.vnum_-1] = val
# 加入一條邊
def add_edge(self, v1, v2, val):
if self.vertex_invalid(v1) or self.vertex_invalid(v2):
raise IndexError('頂點下標越界！')
self.mat_[v1][v2] = val
# 獲取任意邊的信息
def get_edge(self, v1, v2):
if self.vertex_invalid(v1) or self.vertex_invalid(v2):
raise IndexError('頂點下標越界！')
return self.mat_[v1][v2]
# 獲取所有的出邊信息
@staticmethod
def out_edges(row, unconn):
output = []
for i in range(len(row)):
if row[i] != unconn:
output.append([i, row[i]])
return output
if __name__ == '__main__':
mat = [[1,0,0,1], [0,1,0,0], [0,0,1,0], [1,0,0,1]]
sample = Graph_mat(mat)
print(sample.mat_)
print('\n')
print(sample.get_v_count())
print('\n')
sample.add_vertex(3)
print(sample.mat_)
print('\n')
print(sample.get_edge(1, 2))
print('\n')
print(sample.out_edges(sample.mat_[0], 0))
鄰接表表示法實現
class Graph_AL:
def __init__(self, mat=[], unconn=0):
vnum = len(mat)
for x in mat:
if len(x) != vnum:
raise ValueError('mat必須是一個標準的鄰接矩陣！')
self.mat_ = [Graph_AL.out_edges(mat[i], unconn) for i in range(vnum)]
self.vnum_ = vnum
self.unconn_ = unconn
# 獲取所有頂點數目
def get_v_count(self):
return self.vnum_
# 判斷頂點下標是否越界
def v_invalid(self, v):
return v < 0 or v >= self.vnum_
# 加入頂點
def add_vertex(self, val):
self.mat_.append([])
self.vnum_ += 1
# 加入邊
def add_edge(self, v1, v2, val):
if self.vnum_ == 0:
raise GraphError('頂點數量小於2，無法形成邊！')
if self.v_invalid(v1) or self.v_invalid(v2):
raise IndexError('頂點下標越界！')
row = self.mat_
i = 0
while i < len(row):
# 如果已經存在這條邊的連接，那麼只需要修改權值
if row[i][0] == v2:
self.mat_[v1][v2] == [v2, val]
return
# 如果不存在這條邊，那麼跳出循環直接insert
if row[i][0] > v2:
break
i += 1
self.mat_[v1].insert(i, [v2, val])
# 獲取邊的信息
def get_edge(self, v1, v2):
if self.vnum_ == 0:
raise GraphError('頂點數量小於2，無法形成邊！')
if self.v_invalid(v1) or self.v_invalid(v2):
raise IndexError('頂點下標越界！')
for i, val in self.mat_[v1]:
if i == v2:
return val
return self.unconn_
# 獲取所有的出邊信息
@staticmethod
def out_edges(row, unconn):
output = []
for i in range(len(row)):
if row[i] != unconn:
output.append([i, row[i]])
return output
if __name__ == '__main__':
mat = [[1,0,0,1], [0,1,0,0], [0,0,1,0], [1,0,0,1]]
sample = Graph_AL(mat)
print(sample.mat_)
print('\n')
print(sample.get_v_count())
print('\n')
sample.add_vertex(3)
print(sample.mat_)
print('\n')
print(sample.get_edge(0, 3))
print('\n')
參考資料
- 裘宗燕.數據結構與算法——Python語言描述[M].北京：機械工業出版社，2015: 224-229。
- 菜鳥教程：Python staticmethod函數
