Chuyển tới nội dung chính
Z Graph & Pathfinding

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.

Miễn phí Không cần đăng ký Chạy trên trình duyệt Tôn trọng riêng tư Updated

Move the indigo token with ↑ ↓ ← → / WASD (or tap an adjacent cell) from the green start to the red goal. Walls block you.

Moves: Time: 🎉 Reached the goal!
/

Mã giả

Cách dùng

  1. 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. 2 Nhấn Play để xem BFS mở rộng theo từng lớp tính từ điểm bắt đầu.
  3. 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. 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.

Tính năng

Hoạt ảnh từng bước

Xem hàng đợi mở rộng biên (frontier) từng cấp một.

Độ phức tạp

Thời gian: O(V + E). Không gian: O(V). Tìm đường đi ngắn nhất trong đồ thị không trọng số.

Riêng tư 100%

Chạy hoàn toàn trong trình duyệt của bạn — không có gì được tải lên.

Ví dụ

Input

graph 1–2, 1–3, 2–4, 3–4; start 1

Output

visit order: 1 → 2 → 3 → 4 (level by level)

Trường hợp sử dụng

  1. 1

    Đường đi ngắn nhất (không trọng số)

    Xem lý do vì sao BFS cho ra đường đi ít cạnh nhất từ đỉnh nguồn.

  2. 2

    Duyệt theo cấp (level-order)

    Khám phá đồ thị hoặc cây theo từng tầng một.

  3. 3

    Tính liên thông & khả năng tiếp cận

    Tìm các đỉnh có thể tiếp cận được từ điểm bắt đầu.

Tóm tắt

Công cụ trực quan hóa BFS của Zerethon mô phỏng thuật toán tìm kiếm theo chiều rộng trên đồ thị ngay trong trình duyệt, khám phá từng cấp một từ đỉnh nguồn bằng cách sử dụng hàng đợi (queue). BFS chạy với thời gian O(V + E) và không gian O(V), đồng thời tìm ra đường đi ngắn nhất (ít cạnh nhất) trong đồ thị không trọng số.

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

Tài liệu tham khảo

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 →

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.

Đăng ký miễn phí