Giáo án điện tử chuyên đề Khoa học máy tính 12 chân trời Bài 3.5: Thực hành kĩ thuật duyệt đồ thị

CHÀO MỪNG CÁC EM ĐẾN VỚI

BÀI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Suy nghĩ và thực hiện hoạt động Khởi động SGK tr.72:

Nêu một ứng dụng của một trong hai thuật toán duyệt đồ thị đã học.

• Ứng dụng của thuật toán duyệt đồ thị theo chiều rộng:
• Kiểm tra một đồ thị là phân đôi (bi-partite).
• Một đồ thị là phân đôi, hay hai phía là một đồ thị G = (V, E) trong đó tập hợp các đỉnh có thể được chia làm hai tập hợp không giao nhau sao cho các đỉnh ở cùng nhóm không kề nhau.

Đồ thị phân đôi

• Ứng dụng của thuật toán duyệt đồ thị theo chiều sâu: Kiểm tra đồ thị có chu trình hay không?

Một đồ thị có chu trình

CHUYÊN ĐỀ 3: TÌM HIỂU KĨ THUẬT DUYỆT ĐỒ THỊ VÀ ỨNG DỤNG

BÀI 3.5: THỰC HÀNH KĨ THUẬT DUYỆT ĐỒ THỊ

Nhiệm vụ 1. Chương trình tìm đường đi bằng thuật toán duyệt đồ thị theo chiều rộng

Yêu cầu: Cho đồ thị vô hướng G. Hãy viết chương trình tìm đường đi từ đỉnh u đến đỉnh v bằng thuật toán duyệt đồ thị theo chiều rộng. Đồ thị G được biểu diễn bằng danh sách kề.

HƯỚNG DẪN

• Sử dụng thuật toán duyệt đồ thị theo chiều rộng, bắt đầu từ đỉnh u.
• Xây dựng mảng một chiều before với giá trị mặc định của các phần tử là –1 để lưu lại các đỉnh trong quá trình duyệt với quy ước: before[i] = j nghĩa là duyệt đỉnh j trước rồi duyệt đỉnh i sau.

• Mã nguồn tham khảo:

0 5

[‘0’, ‘2’, ‘5’]

Đường đi từ đỉnh 0 đến đỉnh 5 là:

0 2 5

Nhiệm vụ 2. Chương trình tìm đường đi bằng thuật toán duyệt đồ thị theo chiều sâu

Yêu cầu: Cho đồ thị G. Hãy viết chương trình tìm đường đi từ đỉnh u đến đỉnh v bằng thuật toán duyệt đồ thị theo chiều sâu. Đồ thị G được biểu diễn bằng danh sách kề.

HƯỚNG DẪN

• Sử dụng thuật toán duyệt đồ thị theo chiều sâu để tiến hành duyệt tất cả các đỉnh mà u có thể liên kết tới trong đồ thị.
• Xây dựng mảng một chiều before với giá trị mặc định của các phần tử là –1 để lưu lại các đỉnh trong quá trình duyệt với quy ước: before[i] = j nghĩa là duyệt đỉnh j trước rồi duyệt đến đỉnh i.

• Mã nguồn tham khảo:

0 5

[‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’]

Đường đi từ đỉnh 0 đến đỉnh 5 là:

0 1 2 3 4 5

LUYỆN TẬP

Nhiệm vụ 1. Tìm đường đi bằng thuật toán duyệt đồ thị theo chiều rộng

Yêu cầu: Bản đồ mô tả đường đi giữa các địa điểm du lịch trong một thành phố được biểu diễn như ở Hình 1. Dựa vào thuật toán duyệt đồ thị theo chiều rộng được biểu diễn bằng ma trận kề, em hãy viết chương trình tìm đường đi từ địa điểm A đến địa điểm D sao cho đi qua ít địa điểm nhất.

Hình 1. Bản đồ thành phố

• Dữ liệu vào: Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đồ thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.
• Dữ liệu ra: Các đỉnh của đường đi từ đỉnh A đến đỉnh D.

Nhiệm vụ 2. Tìm đường đi bằng thuật toán duyệt đồ thị theo chiều sâu

Yêu cầu: Cho bản đồ (Hình 2) gồm các thành phố M, N, P, Q, R được biểu diễn bởi đồ thị. Dựa vào thuật toán duyệt đồ thị theo chiều sâu được biểu diễn bằng ma trận kề, viết chương trình in ra màn hình đường đi từ thành phố M đến thành phố R.

• Dữ liệu vào: Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đồ thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.
• Dữ liệu ra: Các đỉnh của đường đi từ đỉnh M đến đỉnh R.

Hình 2. Địa điểm du lịch

Sử dụng thuật toán duyệt đồ thị theo chiều rộng để viết chương trình tìm đường đi. Thay vì đầu vào là danh sách kề, HS cần chỉnh sửa chương trình cho đầu vào là một ma trận kề.

Nhiệm vụ 1

Sử dụng được thuật toán duyệt đồ thị theo chiều sâu để viết chương trình tìm đường đi. Thay vì đầu vào là danh sách kề, HS cần chỉnh sửa chương trình cho đầu vào là một ma trận kề.

Nhiệm vụ 2

VẬN DỤNG

Nhiệm vụ. Đếm số thành phần liên thông của đồ thị

Một đồ thị G được gọi là không liên thông nếu tồn tại đỉnh u và đỉnh v thuộc G mà không có đường đi giữa hai đỉnh này. Khi đó, đỉnh u và đỉnh v thuộc hai thành phần liên thông khác nhau. Nếu tồn tại đường đi giữa đỉnh u và đỉnh v thì hai đỉnh này phải thuộc cùng một thành phần liên thông. Như vậy, đồ thị G không liên thông sẽ có ít nhất hai thành phần liên thông.

Yêu cầu: Cho đồ thị vô hướng G được biểu diễn bằng danh sách kề. Hãy viết chương trình cho biết số thành phần liên thông của đồ thị G.

- Dữ liệu vào: Tệp dothi.txt chứa dữ liệu của đồ thị G. Hàng đầu tiên là danh sách các đỉnh của đồ thị. Các hàng kế tiếp: mỗi hàng chứa một cạnh gồm hai đỉnh.

- Dữ liệu ra: Số thành phần liên thông của đồ thị G.

VÍ DỤ

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