Sửa chương trình của thuật toán DFS không đệ quy sao cho chương trình trong khi duyệt

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 1 trang 71 Chuyên đề Tin học 12: Sửa chương trình của thuật toán DFS không đệ quy sao cho chương trình trong khi duyệt sẽ in ra các bước với thông tin sau:

– Thông tin ngăn xếp (hiện thời).

– Phần tử được lấy ra từ ngăn xếp.

– Phần tử được đánh dấu để chuẩn bị cho bước sau (mark).

Quảng cáo

Lời giải:

Để sửa đổi chương trình của thuật toán DFS không đệ quy sao cho nó in ra thông tin ngăn xếp hiện thời, phần tử được lấy ra từ ngăn xếp, và phần tử được đánh dấu để chuẩn bị cho bước sau, bạn có thể thực hiện như sau:

def dfs(graph, start):

stack = [start] # Ngăn xếp khởi tạo với đỉnh bắt đầu

visited = set() # Tập hợp các đỉnh đã được thăm

while stack:

# In thông tin ngăn xếp hiện thời

print("Stack hiện thời:", stack)

vertex = stack.pop() # Lấy phần tử từ ngăn xếp

print("Phần tử lấy ra từ ngăn xếp:", vertex)

if vertex not in visited:

print("Phần tử được đánh dấu để chuẩn bị cho bước sau (mark):", vertex)

visited.add(vertex) # Đánh dấu phần tử đã thăm

# Thêm các đỉnh kề vào ngăn xếp

for neighbor in reversed(graph[vertex]):

if neighbor not in visited:

stack.append(neighbor)

return visited

# Đồ 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'

dfs(graph, 'A')

Giải thích:

- Ngăn xếp (Stack): Ban đầu ngăn xếp chứa đỉnh bắt đầu. Mỗi vòng lặp, bạn in ra ngăn xếp hiện thời.

- Phần tử được lấy ra từ ngăn xếp (vertex): Phần tử trên đỉnh ngăn xếp được lấy ra và in ra.

- Phần tử được đánh dấu (mark): Nếu phần tử chưa được thăm, nó được đánh dấu (thêm vào tập visited) và in ra.

Các bước thực hiện:

- Khởi tạo ngăn xếp với đỉnh bắt đầu (start).

- Trong khi ngăn xếp không rỗng:

In thông tin ngăn xếp hiện thời.

Lấy phần tử từ ngăn xếp và in ra.

Nếu phần tử chưa được thăm:

+ Đánh dấu phần tử đã thăm và in ra.

+ Thêm các đỉnh kề vào ngăn xếp theo thứ tự ngược lại để duyệt đúng thứ tự DFS.

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