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ảm giá 50% sách VietJack đánh giá năng lực các trường trên Shopee Mall

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:

Quảng cáo

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

Xem thêm các tài liệu học tốt lớp 12 hay khác:

Tài liệu cho giáo viên: Giáo án, powerpoint, đề thi giữa kì cuối kì, đánh giá năng lực, thi thử THPT, HSG, chuyên đề, bài tập cuối tuần..... độc quyền VietJack, giá hợp lí

Sách VietJack thi THPT quốc gia 2025 cho học sinh 2k7:

ĐỀ THI, GIÁO ÁN, GÓI THI ONLINE DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 12

Bộ giáo án, đề thi, bài giảng powerpoint, khóa học dành cho các thầy cô và học sinh lớp 12, đẩy đủ các bộ sách cánh diều, kết nối tri thức, chân trời sáng tạo tại https://tailieugiaovien.com.vn/ . Hỗ trợ zalo VietJack Official