Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 17: Thực hành duyệt đồ thị tổng hợp

NHIỆT LIỆT CHÀO MỪNG CÁC EM ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Trong bài thực hành trước chúng ta đã được ôn tập và giải một số bài toán có áp dụng thuật toán duyệt đồ thị theo chiều sâu. Còn về thuật toán duyệt theo chiều rộng em có biết gì về các ứng dụng thực tế của bài toán này không?

Tìm kiếm trên đồ thị:

- Tìm kiếm tất cả các đỉnh có thể truy cập được từ một đỉnh cho trước.

- Tìm đường đi ngắn nhất từ một đỉnh này tới một đỉnh khác.

Xác định cấu trúc của đồ thị

- Kiểm tra tính liên thông của đồ thị.

- Tìm số lượng thành phần liên thông trong đô thị.

BÀI 17: THỰC HÀNH DUYỆT ĐỒ THỊ TỔNG HỢP

Tin học 12

Thực hiện nhiệm vụ: Tìm đường đi xe đạp (SGK tr.80)

Hướng dẫn:

Từ dữ liệu đầu vào (tệp Danh-sach.inp và Xe-dap.inp) dễ dàng thiết lập được đồ thị vô hướng G = (V, E) ứng với danh sách kề Adj.

Bài toán: Cho trước hai đỉnh i, j bất kì của đồ thị, cần tìm một đường đi (nếu có) từ i đến j. Giải bằng cách duyệt đồ thị theo chiều rộng, bắt đầu từ đỉnh i, nếu trong quá trình duyệt gặp đỉnh j thì có thể thiết lập đường đi từ i đến j.

Xây dựng chương trình

Hàm BFS(Adj,s) duyệt theo chiều rộng bắt đầu từ đỉnh s sử dụng hai mảng mark[] và prev[]:

• mark[v] = True ↔đỉnh v đã được đánh dấu khi duyệt đồ thị.
• prev[v] = Đỉnh đã được duyệt trước v → u = prev[v] tức là nếu có đường đi từ vị trí s ban đầu đến v thì u sẽ đứng ngay trước v
• Ban đầu mark[] được gán giá trị False, prev[] được gán giá trị None → prev[v] = None, tức là không tồn tại đường đi từ s đến v.

Xây dựng chương trình

Xây dựng chương trình

• Hàm đệ quy printpath(s,t) biểu diễn đường đi từ đỉnh s đến t.
• Sử dụng mảng names[] lưu tên các học sinh trong lớp. Mảng này là kết quả của hàm Getnames(fname).

Xây dựng chương trình

Hàm Getnames(fname) đọc dữ liệu từ tệp Danh-sach.inp và trả về mảng names lưu danh sách tên học sinh của lớp:

Xây dựng chương trình

Hàm BuildGraph(fname) đọc dữ liệu từ tệp Xe-dap.inp và trả về dữ liệu chính của đồ thị vô hướng bao gồm V, Adj.

Xây dựng chương trình

Đoạn chương trình chính giải bài toán:

Lưu ý: Các tệp dữ liệu đầu vào Danh-sach.inp và Xe-dap.inp có thể được đặt cùng vị trí với tệp chương trình.

LUYỆN TẬP

Câu 1:

Sửa lại phần nhập dữ liệu hai học sinh: sẽ nhập trực tiếp tên hai học sinh, kiểm tra các tên này có nhập đúng không và thực hiện yêu cầu như trong chương trình trên.

Câu 2:

Viết lại hàm BFS() trong chương trình trên nhưng sử dụng ma trận kề A thay thế cho danh sách kề Adj.

VẬN DỤNG

Câu 1. Bổ sung thêm yêu cầu của nhiệm vụ trên như sau: Có hay không hai bạn học sinh trong lớp mà không thể đi xe đạp từ nhà bạn này đến nhà bạn kia. Nếu có thì thông báo tên hai bạn học sinh đó.

Gợi ý

VẬN DỤNG

--------------- Còn tiếp ---------------