BFS vs DFS
BFS vs DFS compared — data structure, shortest paths, memory and use cases, with interactive visualizers for both.
Breadth-first search (BFS) explores a graph level by level with a queue; depth-first search (DFS) dives down one branch with a stack (or recursion). Both visit every node in O(V + E) but suit different problems.
BFS vs DFS at a glance
| BFS | DFS | |
|---|---|---|
| Data structure | Queue (FIFO) | Stack / recursion |
| Shortest path (unweighted) | Yes | No |
| Memory | Wide frontier | Path depth |
| Best for | Shortest paths, levels | Cycles, topological sort, mazes |
When to use BFS
Use BFS for shortest paths on unweighted graphs and level-order traversal.
When to use DFS
Use DFS for cycle detection, topological sorting, and exploring all paths.
Tools for BFS & DFS
Trình trực quan Tìm kiếm theo chiều rộng (BFS)
Tìm kiếm theo chiều rộng tương tác trên lưới ô — vẽ tường, di chuyển điểm bắt đầu/đích, sinh mê cung, xem từng bước mở rộng theo từng lớp. Chạy ngay trên trình duyệt.
Mở công cụTrình trực quan hóa Tìm kiếm theo chiều sâu (DFS)
Tìm kiếm theo chiều sâu tương tác trên lưới ô vuông — vẽ tường, di chuyển điểm bắt đầu/đích, tạo mê cung, chạy từng bước quá trình khám phá đào sâu. Chạy ngay trong trình duyệt.
Mở công cụTrình trực quan hóa thuật toán Dijkstra
Trực quan hóa tìm đường Dijkstra trên lưới ô — vẽ tường, di chuyển điểm bắt đầu/đích, tạo mê cung, chạy từng bước quá trình tìm kiếm. Hoạt động ngay trên trình duyệt.
Mở công cụTrình tạo mê cung
Trình tạo mê cung có hoạt ảnh bằng thuật toán chia đệ quy (recursive division) — xem từng bước dựng tường, điều chỉnh tốc độ, tạo mê cung mới. Kết hợp tốt với các trình trực quan hóa thuật toán tìm đường. Chạy hoàn toàn trên trình duyệt.
Mở công cụBFS vs DFS
Thuật toán chia đệ quy tạo mê cung như thế nào?
Nó bắt đầu với một vùng trống, sau đó chia đệ quy mỗi khoang bằng một bức tường thẳng có một khe hở ngẫu nhiên, lặp lại cho đến khi các khoang quá nhỏ để chia tiếp.
Mê cung "hoàn hảo" là gì?
Một mê cung có đúng một đường đi giữa hai ô bất kỳ — không có vòng lặp và không có vùng bị cô lập. Thuật toán chia đệ quy luôn tạo ra mê cung hoàn hảo.
Tôi có thể giải mê cung này không?
Có — sao chép bố cục sang các trình trực quan hóa BFS, Dijkstra hoặc A* (cùng chung lưới ô vuông) để xem thuật toán tìm đường đi qua nó.
Còn những thuật toán tạo mê cung nào khác?
Recursive backtracker (DFS ngẫu nhiên hóa), Prim's, Kruskal's, Wilson's và Eller's — mỗi thuật toán tạo ra mê cung với kết cấu hình ảnh khác nhau.