Tin học 12 · SGK Chuyên đề Khoa học máy tính

Bài 15. Thực hành duyệt đồ thị theo chiều sâu

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

Sau bài học này em sẽ:

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?

Nhiệm vụ: Hệ thống chuyên đề học tập

Trường em từ năm học này sẽ tổ chức mở rất nhiều chuyên đề học tập cho học sinh lựa chọn; các chuyên đề sẽ được học trong các thời gian khác nhau. Các chuyên đề được đánh số từ 0 đến n - 1 với n là số tự nhiên. Tuy nhiên, giữa các chuyên đề có quan hệ ràng buộc kiến thức, ví dụ quan hệ (i, j) chỉ ra muốn học chuyên đề i thì cần học trước chuyên đề j.

Dữ liệu đầu vào dưới dạng tệp văn bản Data.inp như sau:

Hệ thống các chuyên đề của nhà trường được gọi là hợp lí nếu về nguyên tắc mỗi học sinh đều có thể đăng kí để học tất cả các chuyên đề.

Với bộ dữ liệu trên, kiểm tra và thông báo hệ thống chuyên đề có hợp lí hay không.

Với bộ dữ liệu trên thì hệ thống không hợp lí vì nếu em muốn học chuyên đề 1, em phải học chuyên đề 2 trước (dòng 2); muốn học chuyên đề 2 thì cần học chuyên đề 4 trước (dòng 3). Nhưng muốn học chuyên đề 4 thì cần học chuyên đề 1 (dòng 4), điều này mâu thuẫn. Vậy hệ thống chuyên đề trên không hợp lí.

Hướng dẫn

Nếu mỗi chuyên đề là một đỉnh được đánh số từ 0 đến n - 1 và quan hệ ràng buộc kiến thức (i, j) như một cạnh có hướng từ đỉnh i đến đỉnh j thì tập các chuyên đề học tập của trường em sẽ trở thành một mô hình đồ thị có hướng. Trong đồ thị này dễ thấy đồ thị sẽ 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ậy 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.

Ý tưởng của việc kiểm tra này sẽ đượ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ột mảng thể hiện các trạng thái status[] của đồ thị có ý nghĩa như sau:

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 việc kiểm tra chu trình được thực hiện thông qua hai bước sau:

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

def DFS_acyclic(Adj, s):
status[s] = 1  # Đang duyệt
for v in Adj[s]:
if status[v] == 1:
return False
elif status[v] == 0:
if not DFS_acyclic(Adj, v):
return False
status[s] = 2  # Đã duyệt xong
return True

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.

def Acyclic(V, Adj):
for u in V:
if status[u] == 0:
if not DFS_acyclic(Adj, u):
return False
return True

Bộ dữ liệu đầu vào trên chính là tệp danh sách các cạnh của đồ thị có hướng; chúng ta đã biết cách thiết lập hàm BuildGraph(fname) đọc dữ liệu này và trả về tập các đỉnh V và danh sách kề Adj trong Bài 12.

Phần chương trình chính của lời giải bài toán sẽ như sau:

fi = "Data.inp"
V, Adj = BuildGraph(fi)
status = [0] * len(V)
if Acyclic(V, Adj):
print("Hệ thống chuyên đề học tập hợp lí.")
else:
print("Hệ thống chuyên đề học tập không hợp lí.")

Bài 15. Thực hành duyệt đồ thị theo chiều sâu