Chúng ta đã biết về BFS thực sự là gì? nếu không thì không cần phải cảm thấy tồi tệ, chỉ cần đọc toàn bộ bài viết và truy cập bài viết trước của chúng tôi trên Tìm kiếm đầu tiên theo chiều rộng để hiểu rõ hơn. BFS là một trình duyệt theo thứ tự cấp trong đó chúng ta truy cập các nút của cây nhị phân từ trái sang phải ở mọi cấp.
Bằng cách sử dụng một Cấu trúc dữ liệu hàng đợi, chúng tôi tìm thấy trình tự cấp. Chúng tôi bắt đầu từ root sau đó chúng tôi chèn root vào BFS và chèn tất cả các hàng xóm của nút đó vào hàng đợi. Sau đó, bật nút khỏi hàng đợi và thêm nó vào BFS nếu nó không được truy cập và thêm tất cả những người hàng xóm [không được truy cập] vào hàng đợi. Lặp lại nó cho đến khi kích thước của hàng đợi không bằng null.
Tìm kiếm đầu tiên theo chiều sâu [DFS]
Chúng ta cũng biết DFS thực sự là gì? Bạn có thể truy cập bài viết trước của chúng tôi trên Tìm kiếm sâu đầu tiên. DFS của một BT là ba loại truyền tải:
- Đặt hàng trước Traversal
- Inorder Traversal
- Truyền tải đơn đặt hàng
Đặt hàng trước Traversal
Algorithm: Preorder[root]: Step:1 Print the data of the Node. Step:2 Move to the left side of the node[traverse left-subtree]. Step:3 Move to the right side of the node[traverse right-subtree].Inorder Traversal
Algorithm: Inorder[root]: Step:1 Move to the left side of the node[traverse left-subtree]. Step:2 Print the data of the Node. Step:3 Move to the right side of the node[traverse right-subtree].Truyền tải đơn đặt hàng
Algorithm: Postorder[root]: Step:1 Move to the left side of the node[traverse left-subtree]. Step:2 Move to the right side of the node[traverse right-subtree]. Step:3 Print the data of the Node.Dsự khác biệt giữa BFS và DFS của cây nhị phân
Loại cấu trúc dữ liệu được sử dụng
Trong BFS, chúng tôi sử dụng hàng đợi loại cấu trúc dữ liệu và trong DFS, chúng tôi sử dụng ngăn xếp kiểu cấu trúc dữ liệu.
Không gian phức tạp
Trong BFS, chúng tôi sử dụng một hàng đợi để lưu trữ các phần tử của mức để không gian tối đa được sử dụng trong BFS là O [w] trong đó w là phần tử lớn nhất trong một cấp. Trong DFS, chúng tôi sử dụng ngăn xếp và tuân theo khái niệm chiều sâu. Vì vậy, chiều cao tối đa của cây đang chiếm không gian tối đa để đánh giá. Vì vậy, độ phức tạp không gian của DFS là OH] với H là chiều cao của cây.
Thời gian phức tạp
Hiện độ phức tạp của cả hai trường hợp sẽ là O [N + E] trong đó N biểu thị tổng số nút trong BT và E biểu thị tổng số cạnh trong BT.
Tìm kiếm một nút gần nhất với nút gốc
Để có được kết quả tốt nhất, chúng tôi sử dụng BFS để tìm kiếm loại nút gần nút gốc nhất vì nó tuân theo trình tự cấp.
Tìm kiếm một nút từ nút gốc
Để có được kết quả tốt nhất, chúng tôi sử dụng DFS trong trường hợp này vì nó tuân theo khái niệm chiều sâu.
Ý nghĩa
BFS nghĩa là tìm kiếm theo chiều rộng và DFS nghĩa là tìm kiếm theo chiều sâu.
Loại cấu trúc dữ liệu được sử dụng
BFS sử dụng cấu trúc dữ liệu kiểu Hàng đợi và DFS sử dụng cấu trúc dữ liệu kiểu Ngăn xếp.
Căn bản
BFS là một thuật toán dựa trên đỉnh và DFS là một thuật toán dựa trên cạnh.
Tốc độ
BFS chậm hơn DFS.
Tài liệu tham khảo
Các câu hỏi phỏng vấn
| Thuật toán tìm kiếm theo chiều sâu | |
|
Tìm kiếm ưu tiên chiều sâu bắt đầu thăm đỉnh A, đi theo cạnh trái, tiếp tục tìm kiếm xong ở cây con trái mới chuyển sang tìm kiếm ở cây con phải. Thứ tự thăm viếng các đỉnh là: A, B, D, F, E, C, G. Quá trình viếng thăm các đỉnh diễn ra như sau: Sau khi thăm đỉnh A, vì B chưa được thăm nên theo cạnh AB ta thăm B, tiếp tục theo cạnh BD tới viếng thăm D. Từ D không thể tiếp tục đi xa hơn, ta quay lại B. Từ B, theo BF đến thăm F, tiếp tục theo cạnh FE đến thăm E. Từ E cũng không thể đi xa hơn, quay lại A, duyệt tiếp đến C, G. Kết quả của thuật toánSửa đổiMột cách tự nhiên, kết quả của giải thuật tìm kiếm theo chiều sâu là một cây phủ qua tất cả các đỉnh được duyệt của đồ thị. Duyệt các đỉnhSửa đổiCó thể dùng giải thuật này để tạo một danh sách tuyến tính các đỉnh của một đồ thị [hoặc cây]. Có ba cách hiện thực phương pháp này:
Ý tưởng thuật toánSửa đổi
Mệnh đềSửa đổiGọi G là một đồ thị vô hướng, trên đó ta sẽ thực hiện thao tác DFS với đỉnh bắt đầu là s thì:
Chứng minhSửa đổi
Độ phức tạp của thuật toánSửa đổi
Xác định đỉnh kề trong DFSSửa đổi
Xác định đỉnh kề trong Depth-first search
Bắt đầu từ A và kết thúc tại G
Bắt đầu từ A nhưng đi theo trình tự tập các cạnh đã thăm. Chạy từng bước thuật toánSửa đổiGiờ ta sẽ chạy từng bước thuật toán theo ví dụ trên. Nguyên lý[2]Sửa đổiKhởi đầu từ một đỉnh, đi theo các cung[cạnh] xa nhất có thể. Trở lại đỉnh của cạnh xa nhất, tiếp tục duyệt như trước, cho đến đỉnh cuối cùng.
Thuật toán Depth-first search
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 1
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 2
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 3
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 4
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 5
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 6
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 7
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 8
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 9
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 10
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 11
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 12
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 13
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 14
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 15
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 16
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 17
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 18
Chạy từng bước thuật toán Depth-first search trong đồ thị vô hướng, bước 19 Nhiều giải thuật sử dụng tìm kiếm theo chiều sâu:
Tìm kiếm theo chiều rộng
Video demo thuật toán DFS
Video liên quanChủ Đề |