Triển khai đồ thị DSA
Triển khai đồ thị cơ bản
Trước khi có thể chạy các thuật toán trên Biểu đồ, trước tiên chúng ta phải triển khai nó bằng cách nào đó.
Để triển khai Biểu đồ, chúng ta sẽ sử dụng Ma trận kề , giống như ma trận bên dưới.
và ma trận kề của nó
Để lưu trữ dữ liệu cho mỗi đỉnh, trong trường hợp này là các chữ cái A, B, C và D, dữ liệu được đặt trong một mảng riêng khớp với các chỉ mục trong ma trận kề, như sau:
vertexData = [ 'A', 'B', 'C', 'D'] Đối với Đồ thị vô hướng và không có trọng số, như trong hình trên, cạnh giữa đỉnh i và j được lưu trữ với giá trị 1 . Nó được lưu dưới dạng 1 ở cả hai vị trí (j,i) và (i,j) vì cạnh đi theo cả hai hướng. Như bạn có thể thấy, ma trận trở nên đối xứng theo đường chéo đối với các Đồ thị vô hướng như vậy.
Hãy nhìn vào một cái gì đó cụ thể hơn. Trong ma trận kề ở trên, đỉnh A nằm trên chỉ số 0 và đỉnh D nằm trên chỉ số 3 , vì vậy chúng ta lấy cạnh giữa A và D được lưu dưới dạng giá trị 1 ở vị trí (0,3) và (3,0) , bởi vì cạnh đi theo cả hai hướng.
Dưới đây là cách triển khai cơ bản của Đồ thị vô hướng từ hình ảnh trên.
Ví dụ
Trăn:
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) Chạy Ví dụ »Việc triển khai này về cơ bản chỉ là một mảng hai chiều, nhưng để hiểu rõ hơn về cách các đỉnh được kết nối bởi các cạnh trong Biểu đồ mà chúng ta vừa triển khai, chúng ta có thể chạy hàm này:
Ví dụ
Trăn:
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 Chạy ví dụ »Triển khai đồ thị bằng cách sử dụng các lớp
Cách thích hợp hơn để lưu trữ Biểu đồ là thêm một lớp trừu tượng bằng cách sử dụng các lớp sao cho các đỉnh, cạnh và các phương thức liên quan của Biểu đồ, như các thuật toán mà chúng ta sẽ triển khai sau, được chứa ở một nơi.
Các ngôn ngữ lập trình có chức năng hướng đối tượng tích hợp như Python và Java, giúp việc triển khai Đồ thị bằng cách sử dụng các lớp dễ dàng hơn nhiều so với các ngôn ngữ như C mà không có chức năng tích hợp này.
và ma trận kề của nó
Đây là cách Biểu đồ vô hướng ở trên có thể được triển khai bằng cách sử dụng các lớp.
Ví dụ
Trăn:
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() Chạy Ví dụ »Trong đoạn mã trên, tính đối xứng ma trận mà chúng ta nhận được cho Đồ thị vô hướng được cung cấp cho dòng 9 và 10, và điều này giúp chúng ta tiết kiệm một số mã khi khởi tạo các cạnh trong Đồ thị trên các dòng 29-32.
Thực hiện đồ thị có hướng và có trọng số
Để triển khai Biểu đồ có hướng và có trọng số, chúng ta chỉ cần thực hiện một số thay đổi so với cách triển khai Biểu đồ vô hướng trước đó.
Để tạo Đồ thị có hướng, chúng ta chỉ cần loại bỏ dòng 10 trong đoạn mã ví dụ trước, để ma trận không tự động đối xứng nữa.
Thay đổi thứ hai chúng ta cần thực hiện là thêm đối số weight vào phương thức add_edge() , để thay vì chỉ có giá trị 1 để chỉ ra rằng có một cạnh giữa hai đỉnh, chúng ta sử dụng giá trị trọng số thực tế để xác định cạnh.
và ma trận kề của nó.
Dưới đây là cách thực hiện Biểu đồ có hướng và có trọng số ở trên.
Ví dụ
Trăn:
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() Chạy ví dụ » Dòng 3: Ban đầu tất cả các cạnh được đặt thành None .
Dòng 7: Giờ đây, trọng số có thể được thêm vào một cạnh bằng đối số weight bổ sung.
Dòng 10: Bằng cách loại bỏ dòng 10, Biểu đồ hiện có thể được thiết lập theo hướng dẫn.
Ở trang tiếp theo, chúng ta sẽ xem cách duyệt qua Đồ thị và trên các trang tiếp theo sau đó, chúng ta sẽ xem xét các thuật toán khác nhau có thể chạy trên cấu trúc dữ liệu Đồ thị.
