Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 15: Thực hành duyệt đồ thị theo chiều sâu

CHÀO CẢ LỚP! CHÀO MỪNG CÁC EM TỚI BUỔI HỌC NÀY!

Tin học 12

KHỞI ĐỘNG

Trong lí thuyết đồ thị, chu trình được định nghĩa là một đường đi không tầm thường khép kín, tức là đường đi có số cạnh lớn hơn 1 và đỉnh xuất phát trùng với đỉnh kết thúc. Làm cách nào để kiểm tra một đồ thị cho trước có chu trình hay không?

Đồ thị có chu trình

Có thể sử dụng thuật toán DFS duyệt theo chiều sâu để kiểm tra một đồ thị cho trước có chu trình hay không:

• Bắt đầu từ một đỉnh bất kì trong đồ thị.
• Thực hiện duyệt DFS từ đỉnh này.
• Nếu đỉnh nào đã được thăm trước đó và không phải là đỉnh cha của đỉnh hiện tại (trong trường hợp của cây) → tìm thấy một chu trình.
• Nếu tất cả các đỉnh đều đã được duyệt và không tìm thấy chu trình, đồ thị không chứa chu trình.

BÀI 15: THỰC HÀNH DUYỆT ĐỒ THỊ THEO CHIỀU SÂU

Thực hành cá nhân: thực hiện Nhiệm vụ SGK tr.72.

Nếu coi tập hợp các chuyên đề học tập của trường em là một mô hình đồ thị thì:

• Mỗi chuyên đề là một đỉnh được đánh số từ 0 đến n – 1.
• Mỗi quan hệ ràng buộc kiến thức (i, j) là một cạnh có hướng từ đỉnh i đến đỉnh j.

Đồ thị là đồ thị có hướng.

Đồ thị này có chu trình tương đương với tính hợp lí của hệ thống các chuyên đề không?

Đồ thị này không có chu trình tương đương với tính hợp lí của hệ thống các chuyên đề.

Với bài toán trên chúng ta cần kiểm tra xem đồ thị các chuyên đề có chu trình hay không.

Hãy trình bày ý tưởng của việc kiểm tra.

Ý tưởng của việc kiểm tra được thực hiện bằng cách duyệt theo chiều sâu của đồ thị, bắt đầu từ một đỉnh bất kì. Để thực hiện được việc này chúng ta sẽ đưa vào mảng tổng thể các trạng thái status[] của đồ thị.

status[v] = 0 nếu đỉnh v chưa được xét (hoặc duyệt).

status[v] = 1 chỉ ra đỉnh này đang trong quá trình duyệt.

status[v] = 2 nếu đỉnh này đã được duyệt xong.

Công cụ kiểm tra chu trình được thực hiện như thế nào?

Bước 1:

Hàm DFS_acyclic(Adj,s) kiểm tra trong quá trình duyệt bắt đầu từ đỉnh s có gặp chu trình hay không.

Bước 2:

Tiến hành thực hiện kiểm tra trên toàn bộ các đỉnh của đồ thị.

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

Hàm DFS_acyclic(Adj,s) sẽ trả lại True nếu vùng duyệt từ s không có chu trình, ngược lại nếu có chu trình sẽ trả về False.

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

Hàm Acyclic(V,Adj) sẽ kiểm tra trên toàn bộ đồ thị và trả về True nếu đồ thị không có chu trình, ngược lại trả về False.

Phần chương trình chính:

Chương trình đầy đủ

LUYỆN TẬP

Câu 1. Hàm kiểm tra chu trình của đồ thị trên còn đúng không nếu đồ thị ban đầu là vô hướng?

Không đúng. Hàm kiểm tra trên chỉ áp dụng cho đồ thị có hướng. Với đồ thị vô hướng cần chỉnh sửa để có thể áp dụng.

Câu 2. Viết lại hàm kiểm tra chu trình DFS_acyclic(Adj,s) trong chương trình trên nhưng sử dụng phương án không đệ quy của thuật toán DFS.

Hàm DFS_acyclic(Adj,s) có thể viết lại nếu sử dụng phương án không đệ quy như sau:

- status[v] = 0 nếu s chưa được duyệt.

- status[v] = 1 nếu s đã được duyệt và vẫn đang nằm trong ngăn xếp S của lệnh duyệt theo chiều sâu.

- status[v] = 2 nếu s đã được duyệt và đã ra khỏi ngăn xếp S.

VẬN DỤNG

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