Câu hỏi:

11/07/2024 115

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:

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: (ảnh 1)

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

Trả lời:

verified
Giải bởi Vietjack

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

Bình luận


Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

Ý tưởng chính của DFS: 

DFS hoạt động bằng cách bắt đầu từ một đỉnh nguồn, đánh dấu nó là đã thăm, sau đó tiếp tục đi sâu vào các đỉnh kề chưa thăm cho đến khi không thể đi tiếp được nữa. Khi không thể đi tiếp, thuật toán quay lui về các đỉnh trước đó để tiếp tục tìm kiếm các đường đi mới.

Lời giải

Để cài đặt thuật toán duyệt theo chiều sâu (DFS) mà không sử dụng đệ quy, chúng ta có thể sử dụng ngăn xếp (stack) để theo dõi các đỉnh và thực hiện duyệt. Dưới đây là một số cách cài đặt DFS không sử dụng đệ quy:

1. Sử dụng ngăn xếp (Stack):

- Bắt đầu bằng việc đưa một đỉnh bất kỳ vào ngăn xếp.

- Lặp qua các bước sau cho đến khi ngăn xếp trống: 

a) Lấy đỉnh trên cùng của ngăn xếp (top value). 

b) Đánh dấu đỉnh này là đã thăm (thêm vào danh sách visited). 

c) Thêm tất cả các đỉnh kề của đỉnh đang xét vào ngăn xếp, nếu chưa được thăm. 

d) Lặp lại bước a) cho đến khi không còn đỉnh kề nào để thêm vào ngăn xếp.

2. Sử dụng hàng đợi (Queue):

- Tương tự như cách sử dụng ngăn xếp, nhưng thay vì ngăn xếp, chúng ta sử dụng hàng đợi.

- Bắt đầu bằng việc đưa một đỉnh bất kỳ vào hàng đợi.

- Lặp qua các bước sau cho đến khi hàng đợi trống: 

a) Lấy đỉnh đầu tiên của hàng đợi. 

b) Đánh dấu đỉnh này là đã thăm. 

c) Thêm tất cả các đỉnh kề của đỉnh đang xét vào hàng đợi, nếu chưa được thăm. 

d) Lặp lại bước a) cho đến khi không còn đỉnh kề nào để thêm vào hàng đợi.

3. Sử dụng danh sách liên kết (Linked List):

- Thay vì sử dụng ngăn xếp hoặc hàng đợi, chúng ta có thể sử dụng danh sách liên kết để lưu trữ các đỉnh.

- Bắt đầu bằng việc đưa một đỉnh bất kỳ vào danh sách liên kết.

- Lặp qua các bước sau cho đến khi danh sách liên kết trống: 

a) Lấy đỉnh đầu tiên của danh sách liên kết.

b) Đánh dấu đỉnh này là đã thăm. 

c) Thêm tất cả các đỉnh kề của đỉnh đang xét vào danh sách liên kết

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Vietjack official store
Đăng ký gói thi VIP

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

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

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

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

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

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

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

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay