Câu hỏi:
13/07/2024 56Kiểm tra tính liên thông của đơn đồ thị vô hướng
Một đơn đồ thị vô hướng được gọi là liên thông nếu hai đinh bất kì của đồ thị đều có đường đi tới nhau.
Bài toán kiểm tra tính liên thông của đơn đồ thị vô hướng xuất hiện nhiều trong nghiên cứu lí thuyết cũng như ứng dụng trong cuộc sống, sau đây là một ví dụ cụ thể:
Có địa điểm được đánh số từ 0 đến n - 1, có m tuyến xe buýt hai chiều giữa các địa điểm, tuyển thứ k sẽ di chuyển giữa hai địa điểm ik, và jk, Em hãy kiểm tra xem từ một địa điểm bất kì có thể tới được các địa điểm còn lại bằng cách chỉ sử dụng m tuyển xe buýt hay không.
Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 160k).
Quảng cáo
Trả lời:
Sử dụng thuật toán tìm kiếm theo chiều rộng (BFS) hoặc tìm kiếm theo chiều sâu (DFS):
- Bước 1: Biểu diễn đồ thị
Chúng ta sẽ sử dụng danh sách kề (adjacency list) để biểu diễn đồ thị. Giả sử đồ thị có n đỉnh và m cạnh.
def create_adjacency_list(n, edges):
adjacency_list = [[] for _ in range(n)]
for (u, v) in edges:
adjacency_list[u].append(v)
adjacency_list[v].append(u)
return adjacency_list
- Bước 2: Sử dụng BFS hoặc DFS để kiểm tra tính liên thông
Chúng ta sẽ chọn một đỉnh làm điểm bắt đầu (ví dụ đỉnh 0) và sử dụng BFS hoặc DFS để tìm tất cả các đỉnh có thể đi đến từ đỉnh đó. Nếu tất cả n đỉnh đều được thăm, thì đồ thị là liên thông.
def bfs(start, adjacency_list, visited):
queue = [start]
visited[start] = True
while queue:
node = queue.pop(0)
for neighbor in adjacency_list[node]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
- Bước 3: Kiểm tra tất cả các đỉnh đã được thăm
Sau khi thực hiện BFS hoặc DFS, chúng ta kiểm tra xem tất cả các đỉnh đã được thăm hay chưa.
def is_connected(n, edges):
if n == 0:
return True # Không có đỉnh nào, coi như liên thông
adjacency_list = create_adjacency_list(n, edges)
visited = [False] * n
# Sử dụng BFS bắt đầu từ đỉnh 0
bfs(0, adjacency_list, visited)
# Kiểm tra xem tất cả các đỉnh đã được thăm chưa
for v in visited:
if not v:
return False
return True
Ví dụ:
Giả sử chúng ta có 5 địa điểm (đỉnh) và 4 tuyến xe buýt (cạnh):
n = 5
edges = [(0, 1), (1, 2), (2, 3), (3, 4)]
print(is_connected(n, edges))
# Kết quả: True, vì đồ thị này là liên thông
Giả sử chúng ta có 5 địa điểm và 3 tuyến xe buýt:
n = 5
edges = [(0, 1), (1, 2), (3, 4)]
print(is_connected(n, edges))
Vậy False, vì đồ thị này không liên thông (có 2 thành phần liên thông)
Đã bán 152
Đã bán 114
Đã bán 132
Đã bán 47
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Kiểm tra tính liên thông của đơn đồ thị có hướng
Trong đơn đồ thị có hướng, người ta thường quan tâm đến tính liên thông mạnh của đồ thị. Một đồ thị có hướng được gọi là liên thông mạnh nếu từ một đỉnh bất kì của đồ thị có thể đến được tất cả các đỉnh còn lại.
Các bài toán liên quan đến tính liên thông của đơn đồ thị có hướng cũng có nhiều ứng dụng như tính liên thông của đơn đồ thị vô hướng.
Câu 2:
Tìm đường đi ngắn nhất trên đơn đồ thị có hướng
Một dãy đỉnh a = i0, i1,..., is = b (a ≠ b) được gọi là đường đi từ đinh a tới đỉnh b nếu hai đỉnh liên tiếp trên đường đi có cạnh nối.
Trong cuộc sống chúng ta gặp rất nhiều bài toán liên quan đến tìm đường đi, dưới đây là một ví dụ cụ thể.
Có n sân bay được đánh số từ 0 đến n - 1, có m tuyến bay giữa các sân bay, tuyến thứ k sẽ bay từ sân bay i, sang sân bay j .Em hãy tìm cách di chuyển từ sân bay a tới sân bay b với số tuyến bay là ít nhất.
về câu hỏi!