BFS trên ma trận và Backtracking

#1

Chuyện là em mới tập tành học lí thuyết đồ thị. Khi làm bài tập về ma trận yêu cầu dùng BFS thì em lại cảm thấy mình giống như đang áp dụng backtracking vậy. Liệu chúng có khác nhau không ạ? mọi người thông não giùm em với!!

#2

Khác nhau mà, backtracking dựa trên stack :smiley:

4 Likes
#3

vậy nó khác ở chỗ BFS dựa vào các hàng đợi FIFO còn backtracking dựa vào stack LIFO hay sao ạ :dizzy_face:

#4

  • BFS không sử dụng đệ quy mà dùng queue.

  • Backtracking sử dụng đệ quy (<=> dựa trên stack). Trạng thái được lưu lại (tạm thời) trước khi chuyển sang bước tiếp theo, sau đó reset lại để phục vụ cho lần thử mới.

try(i):
    ...
    for (giá trị u cho bước i):
        state[i] = u
        try(i+1)  # bước tiếp theo
        state[i] = 0   # trả lại trạng thái ban đầu cho giá trị u tiếp theo
  • Bonus: DFS mới sử dụng đệ quy, và DFS không phải backtracking vì kết quả của DFS được cập nhật 1 lần duy nhất.
4 Likes
#5

Backtracking chỉ xử lí được cây chứ gặp 1 chu trình thì cứ đi hoài không dừng :slight_smile: do không lưu các trạng thái trung gian như DFS.

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?