Câu hỏi:

11/07/2024 167

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).

Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).

Tổng ôn toán Tổng ôn sử Các môn khác

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Để 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).

Xem đáp án » 11/07/2024 264

Câu 2:

Viết chương trình in ra thứ tự các đỉnh đã được duyệt bằng thuật toán DFS theo cả hai cách đệ quy và không đệ quy, áp dụng cho đồ thị có hướng Hình 14.1b trong phần Khởi động.

Xem đáp án » 11/07/2024 199

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.

Xem đáp án » 11/07/2024 196

Câu 4:

Chúng ta đã biết bài toán và thuật toán duyệt (tìm kiếm) dữ liệu trên các cấu trúc dữ liệu khác nhau:

– Kiểu dữ liệu mảng (một hoặc hai chiều).

– Kiểu dữ liệu cây (cây nhị phân và cây tìm kiếm nhị phân).

Vậy với dữ liệu của đồ thị, việc duyệt các đỉnh của đồ thị sẽ được thực hiện như thế nào? Quan sát hai đồ thị ở Hình 14.1 và thảo luận với bạn cách thực hiện duyệt trên các đỉnh của đồ thị đó.

Chúng ta đã biết bài toán và thuật toán duyệt (tìm kiếm) dữ liệu trên các cấu trúc dữ liệu khác nhau: – Kiểu dữ liệu mảng (một hoặc hai chiều). – Kiểu dữ liệu cây (cây nhị phân và cây tìm kiếm nhị phân). Vậy với dữ liệu của đồ thị, việc duyệt các đỉnh của đồ thị sẽ được thực hiện như thế nào? Quan sát hai đồ thị ở Hình 14.1 và thảo luận với bạn cách thực hiện duyệt trên các đỉnh của đồ thị đó. (ảnh 1)

Xem đáp án » 26/06/2024 115

Câu 5:

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?

Xem đáp án » 11/07/2024 114

Câu 6:

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ì.

Xem đáp án » 11/07/2024 105

Bình luận


Bình luận
Đăng ký gói thi VIP

VIP 1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 2 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 3 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 4 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Siêu tiết kiệm - Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

Vietjack official store