Câu hỏi:
11/07/2024 180
Viết lại hàm BFS() duyệt theo chiều rộng nhưng sử dụng dữ liệu là ma trận kề A của đồ thị.
Viết lại hàm BFS() duyệt theo chiều rộng nhưng sử dụng dữ liệu là ma trận kề A của đồ thị.
Quảng cáo
Trả lời:
Giải bởi Vietjack
Gợi ý viết tổng quát của hàm BFS sử dụng ma trận kề của đồ thị:
from collections import deque
def BFS(matrix, start):
n = len(matrix) # Số lượng đỉnh trong đồ thị
visited = set() # Sử dụng một set để lưu trữ các đỉnh đã được duyệt
queue = deque([start]) # Khởi tạo hàng đợi và thêm đỉnh bắt đầu vào đó
while queue:
vertex = queue.popleft() # Lấy đỉnh ở đầu hàng đợi ra
if vertex not in visited:
print("Visit:", vertex) # In ra đỉnh đã duyệt
visited.add(vertex) # Đánh dấu đỉnh đã duyệt
for neighbor in range(n): # Duyệt qua tất cả các đỉnh
if matrix[vertex][neighbor] == 1 and neighbor not in visited:
queue.append(neighbor) # Thêm các đỉnh kề chưa được duyệt vào hàng đợi
# Đồ thị mẫu dưới dạng ma trận kề
graph_matrix = [
[0, 1, 1, 0, 0, 0], # A
[1, 0, 0, 1, 1, 0], # B
[1, 0, 0, 0, 0, 1], # C
[0, 1, 0, 0, 0, 0], # D
[0, 1, 0, 0, 0, 1], # E
[0, 0, 1, 0, 1, 0] # F
]
# Thực hiện BFS từ đỉnh 0 (tương ứng với đỉnh 'A')
BFS(graph_matrix, 0)
- Chú ý: Trong hàm BFS này, ta sử dụng ma trận kề matrix để xác định các đỉnh kề của mỗi đỉnh. Nếu một đỉnh kề chưa được duyệt, ta thêm nó vào hàng đợi để duyệt tiếp. Quá trình này được lặp lại cho tất cả các đỉnh kề của mỗi đỉnh được duyệt.
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
Sách thầy cô Vietjack biên soạn:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Thứ tự các đỉnh được duyệt khi thực hiện duyệt theo chiều sâu (DFS) và chiều rộng (BFS) bắt đầu từ đỉnh ‘a’:
Duyệt theo chiều sâu (DFS):
- Thứ tự có thể là: a, b, c, d, c, g, b, a, e, f.
Duyệt theo chiều rộng (BFS):
- Thứ tự có thể là: a, b, e, c, f, g, d.
Lời giải
Để kiểm tra xem đồ thị có chu trình hay không, ta có thể sử dụng thuật toán BFS để duyệt đồ thị và kiểm tra xem có đỉnh nào được duyệt lại không. Nếu có đỉnh nào đã được duyệt và nó là đỉnh kề của đỉnh hiện tại, thì đồ thị chứa chu trình.
Dưới đây là một cài đặt Python cho hàm Acycle(G):
from collections import deque
def Acycle(G):
# Hàm kiểm tra có chu trình hay không
def has_cycle(graph, start):
visited = set()
queue = deque([(start, None)]) # Lưu trữ cả cạnh đến đỉnh đang duyệt
while queue:
vertex, parent = queue.popleft()
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor != parent: # Loại bỏ trường hợp quay lại đỉnh cha
if neighbor in visited:
return True # Đồ thị có chu trình
else:
queue.append((neighbor, vertex)) # Thêm đỉnh kề vào hàng đợi
return False # Đồ thị không có chu trình
# Duyệt qua tất cả các đỉnh của đồ thị
for vertex in G:
if has_cycle(G, vertex):
return False # Nếu có chu trình, trả về False
return True # Nếu không có chu trình, trả về True
# Ví dụ về đồ thị được biểu diễn bằng danh sách kề
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# Kiểm tra đồ thị có chu trình hay không
print(Acycle(graph)) # False
- Chú ý: Trong hàm Acycle(G), ta duyệt qua tất cả các đỉnh của đồ thị và sử dụng hàm has_cycle(graph, start) để kiểm tra xem có chu trình bắt đầu từ đỉnh đó hay không. Nếu ta tìm thấy bất kỳ chu trình nào, ta trả về False. Nếu không có chu trình nào được tìm thấy, ta trả về True.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Nhắn tin Zalo