Truyền tải đồ thị DSA
Đồ thị truyền tải
Đi qua một Đồ thị có nghĩa là bắt đầu từ một đỉnh và đi dọc theo các cạnh để thăm các đỉnh khác cho đến khi tất cả các đỉnh hoặc càng nhiều đỉnh càng tốt đã được thăm.
Kết quả:
Hiểu cách duyệt qua Biểu đồ là điều quan trọng để hiểu cách hoạt động của các thuật toán chạy trên Biểu đồ.
Hai cách phổ biến nhất mà Biểu đồ có thể được duyệt là:
- Tìm kiếm theo chiều sâu (DFS)
- Tìm kiếm theo chiều rộng đầu tiên (BFS)
DFS thường được triển khai bằng cách sử dụng Ngăn xếp hoặc bằng cách sử dụng đệ quy (sử dụng ngăn xếp cuộc gọi), trong khi BFS thường được triển khai bằng Hàng đợi .
Ngăn xếp cuộc gọi giữ cho các chức năng chạy theo đúng thứ tự.
Ví dụ: nếu FunctionA gọi FunctionB, FunctionB được đặt lên trên ngăn xếp cuộc gọi và bắt đầu chạy. Khi FunctionB kết thúc, nó sẽ bị xóa khỏi ngăn xếp và sau đó FunctionA sẽ tiếp tục công việc của mình.
Traversal tìm kiếm theo chiều sâu
Tìm kiếm theo chiều sâu được cho là đi "sâu" vì nó thăm một đỉnh, sau đó đến đỉnh liền kề, rồi đến đỉnh liền kề của đỉnh đó, v.v., và theo cách này, khoảng cách từ đỉnh bắt đầu tăng lên cho mỗi lần lặp đệ quy.
Làm thế nào nó hoạt động:
- Bắt đầu truyền tải DFS trên một đỉnh.
- Thực hiện duyệt DFS đệ quy trên mỗi đỉnh liền kề miễn là chúng chưa được truy cập.
Chạy hoạt ảnh bên dưới để xem cách truyền tải Tìm kiếm theo chiều sâu (DFS) chạy trên một Biểu đồ cụ thể, bắt đầu từ đỉnh D (nó giống như hoạt ảnh trước đó).
Kết quả:
Quá trình truyền tải DFS bắt đầu ở đỉnh D, đánh dấu đỉnh D là đã truy cập. Sau đó, với mỗi đỉnh mới được thăm, phương pháp truyền tải được gọi đệ quy trên tất cả các đỉnh liền kề chưa được thăm. Vì vậy, khi đỉnh A được truy cập trong hoạt ảnh ở trên, đỉnh C hoặc đỉnh E (tùy thuộc vào cách triển khai) là đỉnh tiếp theo nơi quá trình truyền tải tiếp tục.
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}")
def dfs_util(self, v, visited):
visited[v] = True
print(self.vertex_data[v], end=' ')
for i in range(self.size):
if self.adj_matrix[v][i] == 1 and not visited[i]:
self.dfs_util(i, visited)
def dfs(self, start_vertex_data):
visited = [False] * self.size
start_vertex = self.vertex_data.index(start_vertex_data)
self.dfs_util(start_vertex, visited)
g = Graph(7)
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_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0) # D - A
g.add_edge(0, 2) # A - C
g.add_edge(0, 3) # A - D
g.add_edge(0, 4) # A - E
g.add_edge(4, 2) # E - C
g.add_edge(2, 5) # C - F
g.add_edge(2, 1) # C - B
g.add_edge(2, 6) # C - G
g.add_edge(1, 5) # B - F
g.print_graph()
print("\nDepth First Search starting from vertex D:")
g.dfs('D')
Chạy Ví dụ » Dòng 60: Quá trình truyền tải DFS bắt đầu khi phương thức dfs() được gọi.
Dòng 33: Mảng visited trước tiên được đặt thành false cho tất cả các đỉnh, vì chưa có đỉnh nào được truy cập tại thời điểm này.
Dòng 35: Mảng visited được gửi dưới dạng đối số cho phương thức dfs_util() . Khi mảng visited được gửi dưới dạng đối số như thế này, nó thực sự chỉ là một tham chiếu đến mảng visited được gửi đến phương thức dfs_util() chứ không phải mảng thực tế có các giá trị bên trong. Vì vậy, luôn chỉ có một mảng visited trong chương trình của chúng ta và phương thức dfs_util() có thể thực hiện các thay đổi đối với mảng đó khi các nút được truy cập (dòng 25).
Dòng 28-30: Đối với đỉnh hiện tại v , tất cả các nút liền kề được gọi đệ quy nếu chúng chưa được truy cập.
Truyền tải tìm kiếm đầu tiên theo chiều rộng
Tìm kiếm đầu tiên theo chiều rộng thăm tất cả các đỉnh liền kề của một đỉnh trước khi thăm các đỉnh lân cận tới các đỉnh liền kề. Điều này có nghĩa là các đỉnh có cùng khoảng cách tính từ đỉnh đầu tiên sẽ được thăm trước khi các đỉnh ở xa đỉnh đầu tiên được thăm.
Làm thế nào nó hoạt động:
- Đặt đỉnh bắt đầu vào hàng đợi.
- Đối với mỗi đỉnh được lấy từ hàng đợi, hãy thăm đỉnh đó, sau đó đặt tất cả các đỉnh liền kề chưa được thăm vào hàng đợi.
- Tiếp tục cho đến khi có đỉnh trong hàng đợi.
Chạy hoạt ảnh bên dưới để xem cách truyền tải Tìm kiếm theo chiều rộng (BFS) chạy trên một Biểu đồ cụ thể, bắt đầu từ đỉnh D.
Kết quả:
Như bạn có thể thấy trong hình động ở trên, quá trình truyền tải BFS truy cập các đỉnh có cùng khoảng cách với đỉnh bắt đầu, trước khi truy cập các đỉnh xa hơn. Vì vậy, ví dụ, sau khi thăm đỉnh A, đỉnh E và C được thăm trước khi thăm B, F và G vì các đỉnh đó ở xa hơn.
Truyền tải tìm kiếm đầu tiên theo chiều rộng hoạt động theo cách này bằng cách đặt tất cả các đỉnh liền kề vào một hàng đợi (nếu chúng chưa được truy cập), sau đó sử dụng hàng đợi để truy cập đỉnh tiếp theo.
Ví dụ mã này cho việc truyền tải Tìm kiếm theo chiều rộng cũng giống như ví dụ về mã Tìm kiếm theo chiều sâu ở trên, ngoại trừ phương thức bfs() :
Ví dụ
Trăn:
def bfs(self, start_vertex_data):
queue = [self.vertex_data.index(start_vertex_data)]
visited = [False] * self.size
visited[queue[0]] = True
while queue:
current_vertex = queue.pop(0)
print(self.vertex_data[current_vertex], end=' ')
for i in range(self.size):
if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True Chạy Ví dụ » Dòng 2-4: Phương thức bfs() bắt đầu bằng cách tạo một hàng đợi có đỉnh bắt đầu bên trong, tạo một mảng visited và đặt đỉnh bắt đầu là đã truy cập.
Dòng 6-13: Quá trình truyền tải BFS hoạt động bằng cách lấy một đỉnh từ hàng đợi, in nó và thêm các đỉnh liền kề vào hàng đợi nếu chúng chưa được truy cập, sau đó tiếp tục lấy các đỉnh từ hàng đợi theo cách này. Quá trình truyền tải kết thúc khi phần tử cuối cùng trong hàng đợi không có đỉnh liền kề nào chưa được duyệt.
Truyền tải DFS và BFS của đồ thị có hướng
Thực tế, việc duyệt theo chiều sâu và chiều rộng có thể được triển khai để hoạt động trên Đồ thị có hướng (thay vì vô hướng) chỉ với rất ít thay đổi.
Chạy hoạt ảnh bên dưới để xem cách duyệt qua Biểu đồ có hướng bằng DFS hoặc BFS.
Kết quả:
Để chuyển từ duyệt qua Đồ thị có hướng thay vì Đồ thị vô hướng, chúng ta chỉ cần xóa dòng cuối cùng trong phương thức add_edge() :
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
Chúng ta cũng phải cẩn thận khi xây dựng Biểu đồ của mình vì các cạnh hiện đã được định hướng.
Ví dụ mã bên dưới chứa cả giao dịch BFS và DFS của Biểu đồ có hướng từ hoạt ảnh ở trên:
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}")
def dfs_util(self, v, visited):
visited[v] = True
print(self.vertex_data[v], end=' ')
for i in range(self.size):
if self.adj_matrix[v][i] == 1 and not visited[i]:
self.dfs_util(i, visited)
def dfs(self, start_vertex_data):
visited = [False] * self.size
start_vertex = self.vertex_data.index(start_vertex_data)
self.dfs_util(start_vertex, visited)
def bfs(self, start_vertex_data):
queue = [self.vertex_data.index(start_vertex_data)]
visited = [False] * self.size
visited[queue[0]] = True
while queue:
current_vertex = queue.pop(0)
print(self.vertex_data[current_vertex], end=' ')
for i in range(self.size):
if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
g = Graph(7)
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_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0) # D -> A
g.add_edge(3, 4) # D -> E
g.add_edge(4, 0) # E -> A
g.add_edge(0, 2) # A -> C
g.add_edge(2, 5) # C -> F
g.add_edge(2, 6) # C -> G
g.add_edge(5, 1) # F -> B
g.add_edge(1, 2) # B -> C
g.print_graph()
print("\nDepth First Search starting from vertex D:")
g.dfs('D')
print("\n\nBreadth First Search starting from vertex D:")
g.bfs('D')
Chạy Ví dụ »Bây giờ chúng ta đã xem xét hai thuật toán cơ bản về cách duyệt qua Biểu đồ, chúng ta sẽ sử dụng các trang tiếp theo để xem các thuật toán khác có thể chạy trên cấu trúc dữ liệu Biểu đồ như thế nào.
