Thực hiện công việc duyệt theo chiều rộng của đồ thị Hình 16.1b, bắt đầu từ đỉnh 0. Các bước thực hiện sẽ duyệt các đỉnh theo trình tự sau:
- Mức 0: Bản thân đỉnh 0.
- Mức 1: Các đỉnh kề với đỉnh mức 0.
- Mức 2: Các đỉnh là kề với đỉnh mức 1. Đỉnh mức 2 là các đỉnh mà tồn tại đường đi từ đỉnh 0 đến đỉnh này theo 2 cạnh, qua đỉnh mức 1.
Quá trình cứ tiếp tục như vậy cho đến khi không thể duyệt thêm được nữa.
Trao đổi, thảo luận nhóm để nhận biết sự khác biệt giữa hai phương pháp duyệt đồ thị theo chiều sâu và chiều rộng khác nhau như thế nào.
Thực hiện công việc duyệt theo chiều rộng của đồ thị Hình 16.1b, bắt đầu từ đỉnh 0. Các bước thực hiện sẽ duyệt các đỉnh theo trình tự sau:
- Mức 0: Bản thân đỉnh 0.
- Mức 1: Các đỉnh kề với đỉnh mức 0.
- Mức 2: Các đỉnh là kề với đỉnh mức 1. Đỉnh mức 2 là các đỉnh mà tồn tại đường đi từ đỉnh 0 đến đỉnh này theo 2 cạnh, qua đỉnh mức 1.
Quá trình cứ tiếp tục như vậy cho đến khi không thể duyệt thêm được nữa.
Trao đổi, thảo luận nhóm để nhận biết sự khác biệt giữa hai phương pháp duyệt đồ thị theo chiều sâu và chiều rộng khác nhau như thế nào.
Quảng cáo
Trả lời:
Giải bởi Vietjack
Để thực hiện duyệt theo chiều rộng (BFS) từ đỉnh 0 của đồ thị, chúng ta sẽ tuân theo các bước sau:
- Mức 0: Bắt đầu từ đỉnh 0.
- Mức 1: Duyệt tất cả các đỉnh kề với đỉnh 0.
- Mức 2: Duyệt tất cả các đỉnh kề với các đỉnh ở Mức 1 và không phải là đỉnh 0.
- Các Mức tiếp theo: Tiếp tục duyệt các đỉnh kề với đỉnh ở mức trước đó, không lặp lại các đỉnh đã duyệt.
Quá trình này tiếp tục cho đến khi tất cả các đỉnh có thể tiếp cận từ đỉnh 0 đều được duyệt.
Sự khác biệt chính giữa hai phương pháp duyệt đồ thị theo chiều sâu (DFS) và chiều rộng (BFS) là:
- DFS: Duyệt sâu vào từng nhánh của đồ thị trước khi quay lại (backtrack).
- BFS: Duyệt đồ thị theo từng mức độ rộng, từ gần đến xa so với điểm bắt đầu.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Đang tải chế độ Học...
Hot: 1000+ đề thi giữa kì 1 lớp 1-12 đầy đủ các môn (Update 2026) (chỉ từ 60k). Tải ngay
Đăng ký VIP để học và luyện thi không giới hạn
Trọn bộ quyền lợi trên Vietjack, trong một tài khoản.
- Phòng luyện thi cấp tốc: ĐGNL - ĐGTD, Tốt nghiệp THPT, Ôn vào 10, Ôn vào 6, Ôn Giữa kì/Cuối kì
- Hơn 200K đề thi thử, đề minh hoạ, chính thức các năm
- Với 3tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
- Tải xuống đề thi [DOCX] với đầy đủ đáp án
- Xem hàng ngàn bài giảng đính kèm củng cố thêm kiến thức
- Bao gồm tất cả các bậc từ Tiểu học đến Đại học
- Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện
- Đăng ký ngay
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
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.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
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.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng ký để học cùng Vietjack. Hoàn toàn miễn phí!
Bằng việc đăng ký, bạn đồng ý với Điều khoản sử dụng và Chính sách bảo mật của Vietjack.
Nhắn tin Zalo
Hỏi bài tập