圖是一種抽象資料結構,本質和樹狀結構是一樣的。
圖與樹比較,圖具有封閉性,可以把樹結構看成是圖結構的前生。如果將兄弟節點或子節點之間的水平連接應用於樹狀結構,則可以建立圖形結構。
樹適合描述從上向下的一對多的資料結構,如公司的組織結構。
圖適合描述更複雜的多對多資料結構,如複雜的群體社交關係。
借助電腦解決現實世界中的問題時,除了儲存現實世界中的訊息,也需要正確地描述訊息之間的關係。
如在開發地圖程式時,需要在電腦中正確模擬出城市與城市、或城市中各道路之間的關係圖。只有在這個基礎上,才能用演算法計算出從一個城市到另一個城市,或從指定起點到目標點的最佳路徑。
類似的還有航班路線圖、火車線圖、社交交系圖。
圖結構可以有效地反映現實世界中如上所述資訊之間的複雜關係。以此可使用演算法方便的計算出如航班線路中的最短路徑、如火車線路中的最佳中轉方案,如社交圈中誰與誰關係最好、婚姻網中誰與誰最般配……
頂點:頂點也稱為節點,可認為圖就是頂點組成的集合。頂點本身是有數據意義的,所以頂點都會帶有附加訊息,稱作"有效載荷"。
頂點可以是現實世界中的城市、地名、站名、人……
邊: 圖中的邊用來描述頂點之間的關係。邊可以有方向也可以沒有方向,有方向的邊又可分為單向邊和雙向邊。
如下圖(項點1)到(頂點2)之間的邊只有一個方向(箭頭所示為方向),稱為單向邊。類似現實世界中的單向道。
(頂點1)到(頂點2)之間的邊有兩個方向(雙向箭頭),稱為雙向邊。 城市與城市的關係為雙向邊。
權重: 邊上可以附加價值資訊,附加的值稱為權重。有權重的邊用來描述一個頂點到另一個頂點的連結強度。
如現實生活中的地鐵路線中,權重可以描述兩個車站之間時間長度、公里數、票價……
邊描述的是頂點之間的關係,權重描述的是連結的差異性。
路徑:
#先了解現實世界中路徑概念
如:從一個城市開車到另一個城市,就需要先確定好路徑。也就是 從出發地到目的地要經過那些城市?要走多少里程?
可以說路徑是由邊連接的頂點所組成的序列。因路徑不只一條,所以,從一個項點到另一個項點的路徑描述也不指一種。
在圖結構中如何計算路徑?
沒有權重路徑的長度是路徑上的邊數。
有權重路徑的長度是路徑上的邊的權重總和。
如上圖從(頂點1)到(頂點3)的路徑長度為 8。
環: 從起點出發,最後又回到起點(終點也是起點)就會形成一個環,環是一種特殊的路徑。如上 (V1, V2, V3, V1)
就是一個環。
圖的型別:
綜上所述,圖表可以分為如下幾類:
有向圖: 邊有方向的圖稱為有向圖。
無向圖: 邊沒有方向的圖表稱為無向圖。
加權圖: 邊上面有權重資訊的圖表稱為加權圖。
無環圖: 沒有環的圖形稱為無環圖。
有向無環圖: 沒有環的有向圖,簡稱 DAG。
根據圖的特性,圖資料結構中至少要包含兩類資訊:
所有頂點構成集合訊息,這裡以 V 表示(如地圖程式中,所有城市構在頂點集合)。
所有邊構成集合訊息,這裡用 E 表示(城市與城市之間的關係描述)。
如何描述邊?
邊用來表示項點之間的關係。所以一條邊可以包括 3 個元資料(起點,終點,權重)。當然,權重是可以省略的,但一般研究圖時,都是指的加權圖。
若以 G
表示圖,則 G = (V, E)
。每一邊可以用二元組 (fv, ev)
也可以使用 三元組 (fv,ev,w)
描述。
fv
表示起點,ev
表示終點。且 fv
,ev
資料必須引用於 V
集合。
如上的圖結構可以描述如下:
# 5 个顶点 V={A0,B1,C2,D3,E4} # 7 条边 E={ (A0,B1,3),(B1,C2,4),(C2,D3,6),(C2,E4,1),(D3,E4,2),(A0,D3,5),(E4,B1,7)}
圖的抽象資料描述中至少要有的方法:
Graph ( )
: 用來建立一個新圖。
add_vertex( vert )
:在圖中新增一個節點,參數應該是一個節點類型的物件。
add_edge(fv,tv )
:在 2 個項點之間建立起邊關係。
add_edge(fv,tv,w )
:在 2 個項點之間建立起一邊並指定連線權重。
find_vertex( key )
: 根據關鍵字 key 在圖中尋找頂點。
find_vertexs( )
:查詢所有頂點資訊。
find_path( fv,tv)
:找出.從一個頂點到另一個頂點之間的路徑。
圖的儲存實作主流有 2 種:鄰接矩陣與連結表,本文主要介紹鄰接矩陣。
使用二維矩陣(陣列)儲存頂點之間的關係。
如 graph[5][5]
可以儲存5 個頂點的關係數據,行號和列號表示頂點,第v 行的第w 列交叉的單元格中的數值表示從頂點v 到頂點w 的邊的權重,如 grap[2][3]=6
表示C2 頂點和D3 頂點的有連接(相鄰),權重為6
相鄰矩陣的優點就是簡單,可以清楚表示那些頂點是相連的。由於並非每對頂點之間都存在連接,因此矩陣中存在許多未被利用的空間,通常被稱為「稀疏矩陣」。
只有當每一個頂點和其它頂點都有關係時,矩陣才會填滿。如果圖結構的關係不是太複雜,使用這種結構儲存圖資料會浪費大量的空間。
鄰接矩陣適合表示關係複雜的圖結構,如網路上網頁之間的連結、社交圈中人與人之間的社會關係……
因頂點本身有資料意義,需要先定義頂點型別。
頂點類別:
""" 节(顶)点类 """ class Vertex: def __init__(self, name, v_id=0): # 顶点的编号 self.v_id = v_id # 顶点的名称 self.v_name = name # 是否被访问过:False 没有 True:有 self.visited = False # 自我显示 def __str__(self): return '[编号为 {0},名称为 {1} ] 的顶点'.format(self.v_id, self.v_name)
頂點類別中 v_id
和 v_name
很好理解。為什麼要新增一個 visited
?
這個變數用來記錄頂點在路徑搜尋過程中是否已經被搜尋過,避免重複搜尋計算。
圖類別:圖類別的方法較多,這裡逐方法介紹。
初始化方法
class Graph: """ nums:相邻矩阵的大小 """ def __init__(self, nums): # 一维列表,保存节点,最多只能有 nums 个节点 self.vert_list = [] # 二维列表,存储顶点及顶点间的关系(权重) # 初始权重为 0 ,表示节点与节点之间还没有建立起关系 self.matrix = [[0] * nums for _ in range(nums)] # 顶点个数 self.v_nums = 0 # 使用队列模拟队列或栈,用于广度、深度优先搜索算法 self.queue_stack = [] # 保存搜索到的路径 self.searchPath = [] # 暂省略……
初始化方法用來初始化圖中的資料類型:
一維列表 vert_list
保存所有頂點數據。
二維列表 matrix
保存頂點與頂點之間的關聯資料。
queue_stack
使用清單模擬佇列或堆疊,用於後續的廣度搜尋和深度搜尋。
怎麼使用清單模擬佇列或堆疊?
清單有 append()
、pop()
2 個很價值的方法。
append()
用來在清單中新增數據,且每次都是從清單最後面新增。
pop()
預設從清單最後刪除且彈出數據, pop(參數)
可提供索引值用來從指定位置刪除且彈出資料。
使用 append() 和 pop() 方法就能模擬堆疊,從同一個地方進出資料。
使用 append() 和 pop(0) 方法就能模擬佇列,從後面新增數據,從最前面取得資料
##searchPath :用來保存使用廣度或深度優先路徑搜尋中的結果。
新增節(頂)點方法:#
""" 添加新顶点 """ def add_vertex(self, vert): if vert in self.vert_list: # 已经存在 return if self.v_nums >= len(self.matrix): # 超过相邻矩阵所能存储的节点上限 return # 顶点的编号内部生成 vert.v_id = self.v_nums self.vert_list.append(vert) # 数量增一 self.v_nums += 1
上述方法注意一点,节点的编号由图内部逻辑提供,便于节点编号顺序的统一。
添加边方法
此方法是邻接矩阵表示法的核心逻辑。
''' 添加节点与节点之间的边, 如果是无权重图,统一设定为 1 ''' def add_edge(self, from_v, to_v): # 如果节点不存在 if from_v not in self.vert_list: self.add_vertex(from_v) if to_v not in self.vert_list: self.add_vertex(to_v) # from_v 节点的编号为行号,to_v 节点的编号为列号 self.matrix[from_v.v_id][to_v.v_id] = 1 ''' 添加有权重的边 ''' def add_edge(self, from_v, to_v, weight): # 如果节点不存在 if from_v not in self.vert_list: self.add_vertex(from_v) if to_v not in self.vert_list: self.add_vertex(to_v) # from_v 节点的编号为行号,to_v 节点的编号为列号 self.matrix[from_v.v_id][to_v.v_id] = weight
添加边信息的方法有 2 个,一个用来添加无权重边,一个用来添加有权重的边。
查找某节点
使用线性查找法从节点集合中查找某一个节点。
''' 根据节点编号返回节点 ''' def find_vertex(self, v_id): if v_id >= 0 or v_id <= self.v_nums: # 节点编号必须存在 return [tmp_v for tmp_v in self.vert_list if tmp_v.v_id == v_id][0]
查询所有节点
''' 输出所有顶点信息 ''' def find_only_vertexes(self): for tmp_v in self.vert_list: print(tmp_v)
此方法仅为了查询方便。
查询节点之间的关系
''' 迭代节点与节点之间的关系(边) ''' def find_vertexes(self): for tmp_v in self.vert_list: edges = self.matrix[tmp_v.v_id] for col in range(len(edges)): w = edges[col] if w != 0: print(tmp_v, '和', self.vert_list[col], '的权重为:', w)
测试代码:
if __name__ == "__main__": # 初始化图对象 g = Graph(5) # 添加顶点 for _ in range(len(g.matrix)): v_name = input("顶点的名称( q 为退出):") if v_name == 'q': break v = Vertex(v_name) g.add_vertex(v) # 节点之间的关系 infos = [(0, 1, 3), (0, 3, 5), (1, 2, 4), (2, 3, 6), (2, 4, 1), (3, 4, 2), (4, 1, 7)] for i in infos: v = g.find_vertex(i[0]) v1 = g.find_vertex(i[1]) g.add_edge(v, v1, i[2]) # 输出顶点及边a print("-----------顶点与顶点关系--------------") g.find_vertexes() ''' 输出结果: 顶点的名称( q 为退出):A 顶点的名称( q 为退出):B 顶点的名称( q 为退出):C 顶点的名称( q 为退出):D 顶点的名称( q 为退出):E [编号为 0,名称为 A ] 的顶点 和 [编号为 1,名称为 B ] 的顶点 的权重为: 3 [编号为 0,名称为 A ] 的顶点 和 [编号为 3,名称为 D ] 的顶点 的权重为: 5 [编号为 1,名称为 B ] 的顶点 和 [编号为 2,名称为 C ] 的顶点 的权重为: 4 [编号为 2,名称为 C ] 的顶点 和 [编号为 3,名称为 D ] 的顶点 的权重为: 6 [编号为 2,名称为 C ] 的顶点 和 [编号为 4,名称为 E ] 的顶点 的权重为: 1 [编号为 3,名称为 D ] 的顶点 和 [编号为 4,名称为 E ] 的顶点 的权重为: 2 [编号为 4,名称为 E ] 的顶点 和 [编号为 1,名称为 B ] 的顶点 的权重为: 7 '''
在图中经常做的操作,就是查找从一个顶点到另一个顶点的路径。如怎么查找到 A0 到 E4 之间的路径长度:
从人的直观思维角度查找一下,可以找到如下路径:
{A0,B1,C2,E4}
路径长度为 8。
{A0,D3,E4}
路径长度为 7。
{A0,B1,C2,D3,E4}
路径长度为 15。
在路径查找时,人的思维具有知识性和直观性特点,因此不存在所谓的尝试或碰壁问题。而计算机是试探性思维,就会出现这条路不通,再找另一条路的现象。
所以路径算法中常常会以错误为代价,在查找过程中会走一些弯路。常用的路径搜索算法有 2 种:
广度优先搜索
深度优先搜索
先看一下广度优先搜索的示意图:
广度优先搜索的基本思路:
确定出发点,本案例是 A0 顶点。
以出发点相邻的顶点为候选点,并存储至队列。
从队列中每拿出一个顶点后,再把与此顶点相邻的其它顶点做为候选点存储于队列。
不停重复上述过程,至到找到目标顶点或队列为空。
使用广度搜索到的路径与候选节点进入队列的先后顺序有关系。如第 1 步确定候选节点时 B1
和 D3
谁先进入队列,对于后面的查找也会有影响。
上图使用广度搜索可找到 A0~E4
路径是:
{A0,B1,D3,C2,E4}
其实 {A0,B1,C2,E4}
也是一条有效路径,有可能搜索不出来,这里因为搜索到 B1
后不会马上搜索 C2
,因为 B3
先于 C2
进入,广度优先搜索算法只能保证找到路径,而不能保存找到最佳路径。
编码实现广度优先搜索:
广度优先搜索需要借助队列临时存储选节点,本文使用列表模拟队列。
在图类中实现广度优先搜索算法的方法:
class Graph(): # 省略其它代码 ''' 广度优先搜索算法 ''' def bfs(self, from_v, to_v): # 查找与 fv 相邻的节点 self.find_neighbor(from_v) # 临时路径 lst_path = [from_v] # 重复条件:队列不为空 while len(self.queue_stack) != 0: # 从队列中一个节点(模拟队列) tmp_v = self.queue_stack.pop(0) # 添加到列表中 lst_path.append(tmp_v) # 是不是目标节点 if tmp_v.v_id == to_v.v_id: self.searchPath.append(lst_path) print('找到一条路径', [v_.v_id for v_ in lst_path]) lst_path.pop() else: self.find_neighbor(tmp_v) ''' 查找某一节点的相邻节点,并添加到队列(栈)中 ''' def find_neighbor(self, find_v): if find_v.visited: return find_v.visited = True # 找到保存 find_v 节点相邻节点的列表 lst = self.matrix[find_v.v_id] for idx in range(len(lst)): if lst[idx] != 0: # 权重不为 0 ,可判断相邻 self.queue_stack.append(self.vert_list[idx])
广度优先搜索过程中,需要随时获取与当前节点相邻的节点,find_neighbor()
方法的作用就是用来把当前节点的相邻节点压入队列中。
测试广度优先搜索算法:
if __name__ == "__main__": # 初始化图对象 g = Graph(5) # 添加顶点 for _ in range(len(g.matrix)): v_name = input("顶点的名称( q 为退出):") if v_name == 'q': break v = Vertex(v_name) g.add_vertex(v) # 节点之间的关系 infos = [(0, 1, 3), (0, 3, 5), (1, 2, 4), (2, 3, 6), (2, 4, 1), (3, 4, 2), (4, 1, 7)] for i in infos: v = g.find_vertex(i[0]) v1 = g.find_vertex(i[1]) g.add_edge(v, v1, i[2]) print("----------- 广度优先路径搜索--------------") f_v = g.find_vertex(0) t_v = g.find_vertex(4) g.bfs(f_v,t_v) ''' 输出结果 顶点的名称( q 为退出):A 顶点的名称( q 为退出):B 顶点的名称( q 为退出):C 顶点的名称( q 为退出):D 顶点的名称( q 为退出):E ----------- 广度优先路径搜索-------------- 找到一条路径 [0, 1, 3, 2, 4] 找到一条路径 [0, 1, 3, 2, 3, 4] '''
使用递归实现广度优先搜索算法:
''' 递归方式实现广度搜索 ''' def bfs_dg(self, from_v, to_v): self.searchPath.append(from_v) if from_v.v_id != to_v.v_id: self.find_neighbor(from_v) if len(self.queue_stack) != 0: self.bfs_dg(self.queue_stack.pop(0), to_v)
先看一下深度优先算法的示意图。
深度优先搜索算法和广度优先搜索算法不同的地方在于:深度优先搜索算法将候选节点放在堆栈中。因栈是先进后出,所以,搜索到的节点顺序不一样。
使用循环实现深度优先搜索算法:
深度优先搜索算法需要用到栈,本文使用列表模拟。
''' 深度优先搜索算法 使用栈存储下一个需要查找的节点 ''' def dfs(self, from_v, to_v): # 查找与 from_v 相邻的节点 self.find_neighbor(from_v) # 临时路径 lst_path = [from_v] # 重复条件:栈不为空 while len(self.queue_stack) != 0: # 从栈中取一个节点(模拟栈) tmp_v = self.queue_stack.pop() # 添加到列表中 lst_path.append(tmp_v) # 是不是目标节点 if tmp_v.v_id == to_v.v_id: self.searchPath.append(lst_path) print('找到一条路径:', [v_.v_id for v_ in lst_path]) lst_path.pop() else: self.find_neighbor(tmp_v)
测试:
if __name__ == "__main__": # 初始化图对象 g = Graph(5) # 添加顶点 for _ in range(len(g.matrix)): v_name = input("顶点的名称( q 为退出):") if v_name == 'q': break v = Vertex(v_name) g.add_vertex(v) # 节点之间的关系 infos = [(0, 1, 3), (0, 3, 5), (1, 2, 4), (2, 3, 6), (2, 4, 1), (3, 4, 2), (4, 1, 7)] for i in infos: v = g.find_vertex(i[0]) v1 = g.find_vertex(i[1]) g.add_edge(v, v1, i[2]) # 输出顶点及边a print("-----------顶点与顶点关系--------------") g.find_vertexes() print("----------- 深度优先路径搜索--------------") f_v = g.find_vertex(0) t_v = g.find_vertex(4) g.dfs(f_v, t_v) ''' 输出结果 顶点的名称( q 为退出):A 顶点的名称( q 为退出):B 顶点的名称( q 为退出):C 顶点的名称( q 为退出):D 顶点的名称( q 为退出):E -----------顶点与顶点关系-------------- [编号为 0,名称为 A ] 的顶点 和 [编号为 1,名称为 B ] 的顶点 的权重为: 3 [编号为 0,名称为 A ] 的顶点 和 [编号为 3,名称为 D ] 的顶点 的权重为: 5 [编号为 1,名称为 B ] 的顶点 和 [编号为 2,名称为 C ] 的顶点 的权重为: 4 [编号为 2,名称为 C ] 的顶点 和 [编号为 3,名称为 D ] 的顶点 的权重为: 6 [编号为 2,名称为 C ] 的顶点 和 [编号为 4,名称为 E ] 的顶点 的权重为: 1 [编号为 3,名称为 D ] 的顶点 和 [编号为 4,名称为 E ] 的顶点 的权重为: 2 [编号为 4,名称为 E ] 的顶点 和 [编号为 1,名称为 B ] 的顶点 的权重为: 7 ----------- 深度优先路径搜索-------------- 找到一条路径: [0, 3, 4] 找到一条路径: [0, 3, 1, 2, 4] '''
使用递归实现深度优先搜索算法:
''' 递归实现深度搜索算法 ''' def def_dg(self, from_v, to_v): self.searchPath.append(from_v) if from_v.v_id != to_v.v_id: # 查找与 from_v 节点相连的子节点 lst = self.find_neighbor_(from_v) if lst is not None: for tmp_v in lst[::-1]: self.def_dg(tmp_v, to_v) """ 查找某一节点的相邻节点,以列表方式返回 """ def find_neighbor_(self, find_v): if find_v.visited: return find_v.visited = True # 查找与 find_v 节点相邻的节点 lst = self.matrix[find_v.v_id] return [self.vert_list[idx] for idx in range(len(lst)) if lst[idx] != 0]
递归实现时,不需要使用全局栈,只需要获到当前节点的相邻节点便可。
以上是Python怎麼實現圖的廣度與深度優先路徑搜尋演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!