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.
Click & drag on the grid to draw walls · drag the green and red squares to move start / goal · then press Play. Want a challenge? Hit Tự chơi thử and solve the maze by hand.
Move the indigo token with ↑ ↓ ← → / WASD (or tap an adjacent cell) from the green start to the red goal. Walls block you.
Mã giả
Time · Space
Cách dùng
- 1 Vẽ tường bằng cách click và kéo chuột; kéo điểm bắt đầu màu xanh lá hoặc điểm đích màu đỏ để di chuyển chúng.
- 2 Nhấn Play để xem BFS mở rộng theo từng lớp tính từ điểm bắt đầu.
- 3 Dùng Maze để sinh chướng ngại vật ngay lập tức, hoặc Step để chạy từng ô một.
- 4 Trên lưới không trọng số, đường đi mà BFS tìm được luôn đảm bảo là ngắn nhất (ít ô nhất).
Vì sao dùng công cụ này
- Xem vùng biên (frontier) mở rộng ra ngoài theo từng vòng — đặc trưng riêng của BFS.
- Hiểu vì sao BFS tìm được đường đi ngắn nhất trên đồ thị không trọng số.
- So sánh cách mở rộng đều của BFS với DFS (đào sâu theo một hướng) và A* (nhắm thẳng tới đích).
- Chạy hoàn toàn trên trình duyệt của bạn. Không cần đăng ký, không cần tải lên dữ liệu.
Câu hỏi thường gặp
Tìm kiếm theo chiều rộng là gì?
BFS khám phá một đồ thị theo từng lớp bằng cách sử dụng hàng đợi (queue): nó thăm tất cả các đỉnh lân cận của một nút trước khi chuyển sang các lân cận của chúng. Trên đồ thị không trọng số, thuật toán này tìm ra đường đi ngắn nhất.
Độ phức tạp thời gian của BFS là bao nhiêu?
O(V + E) — mỗi đỉnh và mỗi cạnh chỉ được xét một lần, trong đó V là số đỉnh và E là số cạnh.
BFS có luôn tìm được đường đi ngắn nhất không?
Trên đồ thị không trọng số thì có. Với đồ thị có trọng số, hãy dùng Dijkstra hoặc A*, vì các thuật toán này có tính đến chi phí của từng cạnh.
BFS khác DFS ở điểm nào?
BFS dùng hàng đợi (queue) và mở rộng ra ngoài theo từng vòng (đảm bảo đường đi ngắn nhất trên đồ thị không trọng số); DFS dùng ngăn xếp (stack) và đào sâu hết mức có thể trước khi quay lui (không đảm bảo đường đi ngắn nhất).
Trình trực quan Tìm kiếm theo chiều rộng (BFS) là gì?
Trình trực quan Tìm kiếm theo chiều rộng (BFS) mô phỏng cách BFS khám phá một lưới ô theo từng lớp bằng cấu trúc hàng đợi (queue), mở rộng ra ngoài theo từng vòng tính từ điểm bắt đầu. Trên lưới không trọng số, thuật toán này tìm ra đường đi ngắn nhất, và đường đi đó sẽ được tô sáng khi chạm tới điểm đích.
Trình trực quan Tìm kiếm theo chiều rộng (BFS) là công cụ thuật toán miễn phí của Zerethon Tools. 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. Chạy hoàn toàn trong trình duyệt — không đăng ký, không tải lên.
- Danh mục
- Thuật toán
- Giá
- Miễn phí
- Quyền riêng tư
- Chạy trên trình duyệt
- Đăng ký
- Không cần
Quyền riêng tư
Dữ liệu của bạn không bao giờ rời khỏi trình duyệt trừ khi được nêu rõ. Trình trực quan Tìm kiếm theo chiều rộng (BFS) chạy hoàn toàn phía client — không tải lên máy chủ, không ghi log, không theo dõi dữ liệu bạn nhập.
Mới làm quen? Đọc giải thích từng bước kèm phân tích Big-O: Tìm hiểu Graph Algorithms →
So sánh
Công cụ liên quan
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 trực quan hóa thuật toán tìm đường A*
Tìm đường A* tương tác trên lưới ô vuông với heuristic Manhattan — vẽ tường chắn, 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. Chạy hoàn toàn 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 mô phỏng Bubble Sort
Mô phỏng bubble sort có hoạt ảnh với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và pseudocode. Chạy hoàn toàn trong trình duyệt của bạn.
Mở công cụXây dựng, chia sẻ và phát triển trên Zerethon Social
Đăng ký miễn phí. Kiếm điểm, sưu tầm thành tựu và kết nối với nhà sáng tạo khắp thế giới.