Hàm DFS(Adj,u) có thể viết theo một cách khác, việc kiểm tra đỉnh u đã đánh dấu

Giải Chuyên đề Tin 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu - Kết nối tri thức

Luyện tập 2 trang 71 Chuyên đề Tin học 12: Hàm DFS(Adj,u) có thể viết theo một cách khác, việc kiểm tra đỉnh u đã đánh dấu chưa được đưa vào bên trong hàm như sau:

a) Trong trường hợp này, phần chương trình chính cần viết lại như thế nào?

b) Viết lại toàn bộ chương trình duyệt đồ thị theo chiều sâu theo hàm mô tả trên. Cách duyệt này có tương đương với cách đã thực hiện trong Hoạt động 2 không?

Quảng cáo

Lời giải:

a) Phần chương trình chính cần viết lại:

Phần chính của chương trình sẽ khởi tạo danh sách đánh dấu (mark) và gọi hàm DFS từ đỉnh bắt đầu.

def main(graph, start):

# Khởi tạo mảng đánh dấu cho tất cả các đỉnh

mark = {node: False for node in graph}

# Gọi hàm DFS từ đỉnh bắt đầu

DFS(graph, start, mark)

b) Viết lại toàn bộ chương trình duyệt đồ thị theo chiều sâu:

Dưới đây là toàn bộ chương trình với hàm DFS kiểm tra và đánh dấu đỉnh bên trong hàm:

def DFS(graph, u, mark):

if not mark[u]:

mark[u] = True # Đánh dấu đỉnh u

print("Visit:", u) # In ra đỉnh đang được thăm

for v in graph[u]:

DFS(graph, v, mark)

def main(graph, start):

# Khởi tạo mảng đánh dấu cho tất cả các đỉnh

mark = {node: False for node in graph}

# Gọi hàm DFS từ đỉnh bắt đầu

DFS(graph, start, mark)

# Đồ thị mẫu dưới dạng danh sách kề

graph = {

'A': ['B', 'C'],

'B': ['A', 'D', 'E'],

'C': ['A', 'F'],

'D': ['B'],

'E': ['B', 'F'],

'F': ['C', 'E']

}

# Thực hiện DFS từ đỉnh 'A'

main(graph, 'A')

Giải thích:

1. Hàm DFS:

Kiểm tra nếu đỉnh u chưa được đánh dấu.

Đánh dấu đỉnh u và in ra đỉnh đang được thăm.

Duyệt qua các đỉnh kề của u và gọi đệ quy hàm DFS cho từng đỉnh kề đó.

2. Hàm main:

Khởi tạo danh sách đánh dấu (mark) cho tất cả các đỉnh trong đồ thị.

Gọi hàm DFS từ đỉnh bắt đầu (start).

So sánh với cách đã thực hiện trong Hoạt động 2:

Cách duyệt này về cơ bản là tương đương với cách đã thực hiện trong Hoạt động 2 (không đệ quy) về mặt chức năng, tức là cả hai đều thực hiện duyệt đồ thị theo chiều sâu và đảm bảo tất cả các đỉnh đều được thăm một lần. Tuy nhiên, cách đệ quy này dễ hiểu và ngắn gọn hơn, nhưng có thể gặp vấn đề về ngăn xếp đệ quy nếu đồ thị quá lớn (vượt quá giới hạn ngăn xếp của Python). Trong khi đó, cách không đệ quy thường sử dụng ngăn xếp tự quản lý và phù hợp với các đồ thị lớn hơn trong thực tế.

Quảng cáo

Lời giải bài tập Chuyên đề Tin 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu hay, ngắn gọn khác: