DSA 圖的實現
一個基本的圖實現
在我們可以對圖執行演算法之前，我們必須先以某種方式實現它。
為了實現圖，我們將使用一個 鄰接矩陣，如下面的示例所示。
及其鄰接矩陣
為了儲存每個頂點的資料，在本例中是字母 A、B、C 和 D，資料被放入一個單獨的陣列中，該陣列與鄰接矩陣中的索引匹配，如下所示
vertexData = [ 'A', 'B', 'C', 'D']對於無向且非加權的圖，如上圖所示，頂點 i 和 j 之間的邊儲存的值為 1。它儲存在 (j,i) 和 (i,j) 的兩個位置，因為邊是雙向的。如你所見，對於這種無向圖，矩陣變成對角對稱的。
讓我們看一些更具體的內容。在上圖的鄰接矩陣中，頂點 A 位於索引 0，頂點 D 位於索引 3，因此我們在位置 (0,3) 和 (3,0) 中得到頂點 A 和 D 之間的邊，儲存為值 1，因為邊是雙向的。
下面是上面圖片中無向圖的一個基本實現。
示例
Python
vertexData = ['A', 'B', 'C', 'D']
adjacency_matrix = [
[0, 1, 1, 1], # Edges for A
[1, 0, 1, 0], # Edges for B
[1, 1, 0, 0], # Edges for C
[1, 0, 0, 0] # Edges for D
]
def print_adjacency_matrix(matrix):
print("\nAdjacency Matrix:")
for row in matrix:
print(row)
print('vertexData:',vertexData)
print_adjacency_matrix(adjacency_matrix)這個實現基本上只是一個二維陣列，但為了更好地瞭解圖中頂點如何透過邊連線，我們可以執行這個函式
示例
Python
def print_connections(matrix, vertices):
print("\nConnections for each vertex:")
for i in range(len(vertices)):
print(f"{vertices[i]}: ", end="")
for j in range(len(vertices)):
if matrix[i][j]: # if there is a connection
print(vertices[j], end=" ")
print() # new line使用類實現圖
儲存圖的更合適的方法是新增一個使用類的抽象層，這樣圖的頂點、邊以及相關方法（如我們稍後將實現的演算法）都可以集中在一個地方。
像 Python 和 Java 這樣具有內建面向物件功能的程式語言，比 C 這樣沒有內建功能的語言更容易實現基於類的圖。
及其鄰接矩陣
下面是上面無向圖如何使用類實現的示例。
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
g = Graph(4)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_edge(0, 1) # A - B
g.add_edge(0, 2) # A - C
g.add_edge(0, 3) # A - D
g.add_edge(1, 2) # B - C
g.print_graph()在上面的程式碼中，我們為無向圖獲得的矩陣對稱性在第 9 和 10 行中處理，這為我們在第 29-32 行初始化圖中的邊節省了一些程式碼。
有向圖和加權圖的實現
要實現一個有向且加權的圖，我們只需要對前面無向圖的實現做一些修改。
要建立有向圖，我們只需刪除前面示例程式碼中的第 10 行，這樣矩陣就不再自動對稱了。
我們需要做的第二個更改是向 add_edge() 方法新增一個 weight 引數，這樣，我們就不再僅僅使用值 1 來表示兩個頂點之間存在邊，而是使用實際的權重值來定義邊。
及其鄰接矩陣。
下面是上面有向加權圖的實現。
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[None] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(lambda x: str(x) if x is not None else '0', row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
g = Graph(4)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_edge(0, 1, 3) # A -> B with weight 3
g.add_edge(0, 2, 2) # A -> C with weight 2
g.add_edge(3, 0, 4) # D -> A with weight 4
g.add_edge(2, 1, 1) # C -> B with weight 1
g.print_graph()第 3 行：所有邊最初都設定為 None。
第 7 行：現在可以透過附加的 weight 引數將權重新增到邊。
第 10 行：透過刪除第 10 行，圖現在可以設定為有向的。
在下一頁，我們將學習如何遍歷圖，在接下來的幾頁中，我們將瞭解可以在圖資料結構上執行的不同演算法。
