Bài 17. Thực hành duyệt đồ thị tổng hợp
BÀI 17. THỰC HÀNH DUYỆT ĐỒ THỊ TỔNG HỢP
Sau bài học này em sẽ:
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?
Nhiệm vụ: Tìm đường đi xe đạp
Các bạn học sinh lớp em (được đánh số từ 0 đến n - 1) có nhà ở trải rộng khắp thành phố. Trong thành phố có những đường đi chỉ dành cho xe cơ giới, nhưng cũng có đường đi dành cho xe đạp. Các bạn học sinh lớp em chỉ biết đi xe đạp. Dữ liệu đầu vào gồm hai tệp. Tệp Danh-sach.inp sẽ lưu tên các bạn trong lớp, tên mỗi bạn ghi trên một dòng. Tệp thứ hai, Xe-dap.inp mô tả các con đường có thể đi xe đạp từ nhà một bạn trong lớp đến nhà bạn khác. Tệp này cũng có nhiều dòng, mỗi dòng là hai số tự nhiên i, j cách nhau bởi dấu cách, chỉ ra từ nhà bạn thứ i có thể đi xe đạp được đến nhà bạn j. Các đường đi xe đạp này là hai chiều.
Tệp danh sách lớp học Danh-sach.inp bắt đầu là số tự nhiên n, n dòng tiếp theo mỗi dòng là tên của các bạn học sinh trong lớp.
| Xe- dap. inp |
| 6 |
| 0 1 |
| 1 3 |
| 2 3 |
Tệp Xe-dap.inp lưu thông tin các đường đi xe đạp, có dòng đầu tiên là số tự nhiên n, các dòng tiếp theo, mỗi dòng chỉ một đường đi bằng xe đạp giữa hai bạn học sinh trong lớp được mô tả bằng hai số tự nhiên cách nhau bởi dấu cách.
Yêu cầu của bài toán sau khi nhập dữ liệu như sau:
Còn nếu nhập hai chỉ số i = 0, j = 5 thì kết quả sẽ thông báo như sau:
Không tồn tại đường đi xe đạp từ nhà bạn Hòa đến nhà bạn Vân
Hướng dẫn
Từ dữ liệu đầu vào của bài toán (tệp Danh-sach.inp và Xe-dap.inp) chúng ta dễ dàng thiết lập được đồ thị vô hướng G = (V, E) 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. Bài toán này có thể được giải dễ dàng 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.
Trong hàm BFS sau đây, chúng ta sử dụng hai mảng mark[] và prev[] như sau: mark[v] = True khi và chỉ khi đỉnh v đã được đánh dấu khi duyệt đồ thị.
prev[v] = Đỉnh đã được duyệt trước v. Như vậy, nếu 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 toàn bộ mảng mark[] được gán giá trị False, toàn bộ mảng prev[] được gán giá trị None. Vậy nếu prev[v] = None, tức là không tồn tại đường đi từ s đến v.
Hàm BFS(Adj, s) duyệt theo chiều rộng bắt đầu từ đỉnh s như sau:
def BFS(Adj, s):
Q = Queue()
mark[s] = True
enqueue(Q, s)
while not isEmptyQueue(Q):
v = dequeue(Q)
for u in Adj[v]:
if not mark[u]:
mark[u] = True
prev[u] = v
enqueue(Q, u)Để biểu diễn đường đi từ đỉnh s đến t, chúng ta sử dụng hàm đệ quy printpath(s, t). Trong hàm này 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).
def printpath(s, t):
if t == s:
print(names[s], end=" ")
else:
if prev[t] == None:
print("Không tồn tại đường đi")
else:
printpath(s, prev[t])
print(names[t], end=" ")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: Hàm Getnames(fname) đọc dữ liệu từ tệp Danh-sach.inp và lưu danh sách tên học sinh của lớp:
def Getnames(fname):
f = open(fname, encoding="UTF-8")
n = int(f.readline())
names = []
for i in range(n):
names.append(f.readline().strip())
f.close()
return namesHà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. Hàm này đã có trong Bài 12.
Sau khi tất cả các hàm trên đã được thiết lập, chúng ta có thể viết đoạn chương trình chính giải bài toán như sau:
from Queue import Queue
fname = "Danh-sach.inp"
fdata = "Xe-dap.inp"
names = Getnames(fname)
n = len(names)
V, Adj = BuildGraph(fdata)
mark = [False] * n
prev = [None] * n
st = input("Nhập số thứ tự hai bạn học sinh: ")
s, t = [int(ch) for ch in st.split()]
BFS(Adj, s)
printpath(s, t)