一、圖
1.基本概念
圖是一種抽象的數學結構，研究抽象物件之間的一類二元關系及其拓撲性質，而在計算機的資料結構領域中，圖則是一種復雜的資料結構，
一個圖是一個二元組 G = (V, E)，其中：
- V 是非空有窮的頂點集合，也可以有空圖，
- E 是頂點偶數對的集合，即兩個頂點組成一條邊，
- V 中的頂點也被稱為圖 G 的頂點，E 中的邊也被稱為圖 G 的邊，
圖分為無向圖和有向圖，在無向圖中邊沒有方向，用圓括號表示，例如(v1, v2)，在有向圖中邊是有方向的，用尖括號表示，例如<v1, v2>，
2.一些概念和性質
1.完全圖
完全圖：任意兩個頂點之間都有邊的圖，完全圖有如下性質：
- n 個頂點的無向完全圖有 n*(n-1)/2 條邊，
- n 個頂點的有向完全圖有 n*(n-1) 條邊，
2.路徑
對于圖 G=(V, E)，如果存在頂點序列如 Vi0，Vi1，...，Vin，使得 (Vi0，Vi1）、(Vi1，Vi2）、...(Vin-1，Vin）都是圖的邊，則說從 Vi0 到 Vin 存在路徑，并稱 Vi0，Vi1，...，Vin 是從頂點 Vi0 到 Vin 的一條路徑，對于路徑，還有如下概念：
- 路徑的長度就是該路徑上邊的數量，
- 成環的路徑就是起點和終點相同的路徑，
- 簡單路徑就是不含環的路徑，也就是說除了該路徑的起點和終點可能相同外，其他頂點均不相同，
需要注意的是，從一個頂點到另一個頂點，可能存在路徑，也可能不存在路徑，如果存在路徑，還可能存在多條路徑，
3.連通圖
1）連通
如果在一個無向圖中存在 vi 到 vj 的路徑，則稱這兩個頂點連通，
2）連通無向圖
如果無向圖 G 中任意兩個頂點之間都連通，則稱 G 為連通無向圖，
3）強連通有向圖
如果對于有向圖 G 中任意兩個頂點 vi 和 vj ，從 vi 到 vj 連通并從 vi 到 vj 也連通，則稱 G 為強連通有向圖，
4）帶權圖
如果圖 G 中的每條邊都被賦予一個權值，則稱 G 為帶權圖，可以是有向圖也可以是無向圖，邊的權值可用于表示實際應用中與頂點之間的關聯的有關資訊，帶權的連通無向圖也被稱為網路，
3.抽象資料型別
圖作為一種復雜的資料結構，可以給圖定義如下操作：
ADT Graph:
Graph(self) # 用于創建一個圖
is_empty(self) # 判斷圖是否為空
get_vertex(self) # 獲取頂點數量
get_edge(self) # 獲取邊的數量
add_edge(self, v1, v2) # 添加一條 v1 到 v2 的邊
has_edge(self, v1, v2) # 是否有 v1 到 v2 的邊
print(self) # 列印圖
二、圖的表示和實作
1.鄰接矩陣表示法
圖的最基本表示方法是鄰接矩陣表示法，鄰接矩陣是表示圖中頂點間鄰接關系的矩陣，對于一個有 n 個頂點的圖 G=(V, E)，其鄰接矩陣是一個 n*n 的矩陣，圖中每個頂點對應于矩陣里的一行和一列，
最簡單的鄰接矩陣是以0/1為元素的，即對于圖 G 的鄰接矩陣，當 Aij 為0時，表示頂點 vi 和 vj 無邊， 當 Aij 為1時，表示頂點 vi 和 vj 有邊，鄰接矩陣表示了圖中的頂點數量和頂點間的關系（即邊），每個頂點對應矩陣的一對行列下標，聽過一對下標就可以確定圖中的某條邊是否存在了，
要使用 Python 實作一個圖類，可以使用串列（list）或者 numpy 模塊里的矩陣（array），這里就用串列來實作，即用 list 為元素的 list，具體代碼如下：
1 # 使用鄰接矩陣 2 class Graph: 3 def __init__(self, v): 4 self.V = v 5 self.E = 0 6 self.data = https://www.cnblogs.com/TM0831/p/[[0 for _ in range(v)] for _ in range(v)] 7 8 def is_empty(self): 9 """ 10 判斷圖是否為空 11 :return: 12 """ 13 return self.V == 0 14 15 def get_vertex(self): 16 """ 17 獲取頂點數量 18 :return: 19 """ 20 return self.V 21 22 def get_edge(self): 23 """ 24 獲取邊的數量 25 :return: 26 """ 27 return self.E 28 29 def add_edge(self, v1, v2): 30 """ 31 向圖中增加一條v1到v2的邊 32 :param v1: 頂點 33 :param v2: 頂點 34 :return: 35 """ 36 if not self.data[v1][v2]: 37 self.data[v1][v2] = 1 38 self.data[v2][v1] = 1 39 self.E += 1 40 41 def has_edge(self, v1, v2): 42 """ 43 判斷是否有v1到v2的邊 44 :param v1: 頂點 45 :param v2: 頂點 46 :return: 47 """ 48 return self.data[v1][v2] == 1 49 50 def print(self): 51 """ 52 將圖列印出來 53 :return: 54 """ 55 for i in self.data: 56 print(i)
2.鄰接表表示法
用鄰接矩陣表示也有一定缺點，因為圖的鄰接矩陣經常是稀疏的，即圖中大部分元素表示的都是無邊的值，為了降低圖表示的空間代價，可以使用鄰接表表示法，
所謂鄰接表，就是為圖中每個頂點關聯一個表，其中記錄的是這個頂點的所有鄰接邊，頂點是圖中最基本的部分，通常有標識，也可以順序編號，以便可以通過編號隨機訪問，
要用鄰接表來表示圖，這里可以繼承前面的類 Graph，需要對初始化方法、增加邊等方法進行修改，具體代碼如下：
1 # 使用鄰接表 2 class GraphAL(Graph): 3 def __init__(self, v): 4 super(GraphAL, self).__init__(v) 5 self.V = v 6 self.E = 0 7 self.data = https://www.cnblogs.com/TM0831/p/[[] for _ in range(v)] 8 9 def add_edge(self, v1, v2): 10 """ 11 向圖中增加一條v1到v2的邊 12 :param v1: 頂點 13 :param v2: 頂點 14 :return: 15 """ 16 if v2 not in self.data[v1]: 17 self.data[v1].append(v2) 18 self.data[v2].append(v1) 19 self.E += 1 20 21 def has_edge(self, v1, v2): 22 """ 23 判斷是否有v1到v2的邊 24 :param v1: 頂點 25 :param v2: 頂點 26 :return: 27 """ 28 return v2 in self.data[v1]
三、圖的遍歷
1.深度優先搜索
按照深度優先搜索（Depth-First Search）的方法遍歷整個圖，假設從頂點 v 出發進行搜索，深度優先搜索的做法是：
- 訪問頂點 v，并將其標記為已經訪問過，
- 檢查頂點 v 的鄰接點，并從中取出一個尚未訪問的頂點，從它出發繼續進行深度優先搜索（遞回），若不存在這種鄰接點，則回溯，
- 反復進行上述操作直至從頂點 v 出發可以到達的頂點都已經訪問過，
- 如果圖中還存在尚未訪問過的頂點，則從中選出一個頂點，重復進行上述程序，直至圖中的所有頂點都已訪問過，
2.廣度優先搜索
按照廣度優先搜索（Breadth-First Search）的方法遍歷整個圖，假設從頂點 v 出發進行搜索，廣度優先搜索的做法是：
- 訪問頂點 v，并將其標記為已經訪問過，
- 依次訪問頂點 v 的所有鄰接點，再對每個鄰接點的所有鄰接點依次進行訪問，直至所有的可到達的頂點都被訪問過，
- 如果圖中還存在尚未訪問過的頂點，則從中選出一個頂點，重復進行上述程序，直至圖中的所有頂點都已訪問過，
3.深度優先搜索的實作
前面已經說過，深度優先搜索中包含了一個重復呼叫的程序，因而可以使用遞回來實作深度優先搜索對圖進行遍歷，
在遍歷的程序中，需要對已經訪問過的頂點進行標記，所以定義了一個串列 visited，訪問過的頂點就置為 True，除此之外，還要對訪問的頂點進行記錄，可以用一個串列來保存，定義為 path，具體代碼如下：
1 def graph_dfs(graph: GraphAL, s: int): 2 """ 3 運用深度優先搜索對圖進行遍歷 4 :param graph: 圖 5 :param s: 起點 6 :return: 7 """ 8 global visited, path, start 9 visited = [False] * graph.get_vertex() 10 path = [0] * graph.get_vertex() 11 start = s 12 dfs(graph, s) 13 14 15 def dfs(graph: GraphAL, v: int): 16 """ 17 深度優先搜索 18 :param graph: 圖 19 :param v: 頂點 20 :return: 21 """ 22 visited[v] = True 23 for i in graph.get_adj(v): 24 if not visited[i]: 25 path[i] = v 26 dfs(graph, i)
4.廣度優先搜索的實作
在使用廣度優先搜索對圖進行遍歷的程序中，需要使用到佇列，首先將起點入隊，當佇列非空時，重復執行以下程序：
- 從佇列中隨機取出一個頂點，
- 對該頂點的所有鄰接點進行遍歷，若沒有訪問過，則加入到路徑串列 path 中并標記為訪問過，
當佇列為空時，表明搜索完成，結束遍歷，具體代碼如下：
1 def graph_bfs(graph: GraphAL, s: int): 2 """ 3 運用廣度優先搜索對圖進行遍歷 4 :param graph: 圖 5 :param s: 起點 6 :return: 7 """ 8 global visited, path, start 9 visited = [False] * graph.get_vertex() 10 path = [0] * graph.get_vertex() 11 start = s 12 bfs(graph, s) 13 14 15 def bfs(graph: GraphAL, v: int): 16 """ 17 廣度優先搜索 18 :param graph: 圖 19 :param v: 頂點 20 :return: 21 """ 22 visited[v] = True 23 q = Queue() 24 q.put(v) 25 while not q.empty(): 26 v = q.get() 27 for node in graph.get_adj(v): 28 if not visited[node]: 29 path[node] = v 30 visited[node] = True 31 q.put(node)
5.示例
創建一個無向圖 G，如下：
使用鄰接表來表示這個圖，呼叫之前定義的圖類 GraphAL，再將每條邊依次添加進去，代碼如下：
1 graph_test = GraphAL(10) 2 graph_test.add_edge(0, 1) 3 graph_test.add_edge(1, 2) 4 graph_test.add_edge(1, 6) 5 graph_test.add_edge(2, 3) 6 graph_test.add_edge(2, 7) 7 graph_test.add_edge(3, 4) 8 graph_test.add_edge(3, 8) 9 graph_test.add_edge(5, 6) 10 graph_test.add_edge(7, 8) 11 graph_test.add_edge(8, 9) 12 graph_test.print()
前面搜索程序結束之后，路徑都保存在了串列 path 之中，若我們想要獲取從起點到目標頂點的路徑，就需要從 path 中進行獲取，獲取路徑的方法的代碼如下：
1 def get_path_to(v: int): 2 """ 3 獲取從頂點start到頂點v的路徑 4 :param v: 目標頂點 5 :return: 6 """ 7 x = path[v] 8 result = [v, x] 9 while x != start: 10 x = path[x] 11 result.append(x) 12 print(result[::-1])
最后就是分別使用深度優先搜索和廣度優先搜索對圖進行遍歷，起點為頂點1，目標頂點為頂點8，最終分別使用 get_path_to() 獲取路徑，代碼如下：
1 visited = [] 2 path = [] 3 start = None 4 graph_dfs(graph_test, 0) 5 get_path_to(7) 6 # [0, 1, 2, 3, 8, 7] 7 graph_bfs(graph_test, 0) 8 get_path_to(7) 9 # [0, 1, 2, 7]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/49756.html
標籤：其他
上一篇：【從頭開始學】資料結構02