Câu hỏi:
26/06/2024 28Sử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).
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lờ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.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu (DFS – Depth First Search).
Câu 2:
Nếu áp dụng thuật toán duyệt DFS cho đồ thị có hướng Hình 14.1b trong phần khởi động thì thứ tự các đỉnh được đánh dấu sẽ theo thứ tự nào?
Câu 3:
Tìm hiểu một cách cài đặt khác của thuật toán duyệt theo chiều sâu DFS không sử dụng kĩ thuật đệ quy.
Câu 4:
Mô tả quá trình duyệt theo chiều sâu của đồ thị có hướng trong Hình 14.1b nếu xuất phát từ đỉnh 4.
Câu 5:
Quan sát, thảo luận và tìm hiểu thuật toán duyệt theo chiều sâu trên đồ thị bất kì.
Câu 6:
Thứ tự các đỉnh trong danh sách kề có ảnh hưởng đến thứ tự các đỉnh được duyệt của thuật toán DFS không?
về câu hỏi!