Đã thăm
Trong hàng đợi
Cạnh đã xét

  • Hiện tại
  • Trong hàng đợi
  • Đã thăm
  • Đường đi
Nhấp vào đỉnh để đặt

Tìm hiểu thêm về tìm kiếm theo chiều rộng

Tìm kiếm theo chiều rộng (BFS)

Tìm kiếm theo chiều rộng duyệt đồ thị theo từng vòng: trước hết là mọi đỉnh kề với điểm xuất phát, rồi mọi đỉnh cách hai cạnh, cứ thế tiếp tục. Thuật toán làm điều đó bằng một hàng đợi, vào trước, ra trước. Nhấp vào một đỉnh để bắt đầu từ đó, chọn đích nếu muốn, rồi đi từng bước để xem hàng đợi dài ra và ngắn lại, mỗi đỉnh nhận khoảng cách, và đường đi ngắn nhất hiện ra. Nhấn Phát để xem quá trình tìm kiếm, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Nhấp vào một đỉnh để chọn làm điểm xuất phát; chuyển thao tác nhấp sang Đích rồi nhấp vào đỉnh khác để tìm đường đi ngắn nhất đến đó. Số trên mỗi đỉnh là khoảng cách từ điểm xuất phát, còn hàng dưới đồ thị là hàng đợi. Đồ thị mới tạo một đồ thị khác; chọn số đỉnh và số cạnh. Khi bảng đang được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.

Cách nó hoạt động

  1. Nhấp vào một đỉnh để chọn làm điểm xuất phát. Để tìm đường đi, chuyển thao tác nhấp sang Đích rồi nhấp vào đỉnh khác.
  2. Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình tìm kiếm.
  3. Theo dõi hàng đợi dưới đồ thị và khoảng cách trên mỗi đỉnh. Đồ thị mới tạo một đồ thị khác để thử.

Tìm kiếm theo chiều rộng hoạt động thế nào

Đưa đỉnh xuất phát vào hàng đợi với khoảng cách 0. Rồi lặp lại: lấy đỉnh ở đầu hàng đợi và xét từng đỉnh kề của nó. Đỉnh kề chưa từng thấy được gán khoảng cách lớn hơn đỉnh vừa lấy một đơn vị, ghi nhớ đỉnh đó là đường nó được tới, rồi vào cuối hàng đợi. Các đỉnh kề đã thấy thì bỏ qua. Khi hàng đợi rỗng, mọi đỉnh tới được đều đã có khoảng cách.

Vì sao thuật toán tìm được đường đi ngắn nhất

Hàng đợi trả ra các đỉnh theo thứ tự được tìm thấy, và các đỉnh được tìm thấy theo từng vòng: mọi đỉnh ở khoảng cách 1 vào hàng đợi trước bất kỳ đỉnh nào ở khoảng cách 2, cứ thế tiếp tục. Vì vậy lần đầu một đỉnh được tới, nó được tới bằng đường đi có ít cạnh nhất có thể. Lần theo các đỉnh đã ghi nhớ từ đích về điểm xuất phát sẽ cho đường đi đó. Cách này chỉ đếm cạnh; khi các cạnh có độ dài khác nhau, cần dùng thuật toán Dijkstra.

Câu hỏi thường gặp

Tìm kiếm theo chiều rộng là gì?

Một cách duyệt đồ thị từ một đỉnh xuất phát bằng cách thăm hết các đỉnh kề trước, rồi đến đỉnh kề của chúng, cứ thế theo từng vòng. Thuật toán dùng hàng đợi để giữ các đỉnh theo thứ tự được tìm thấy.

Tìm kiếm theo chiều rộng có tìm được đường đi ngắn nhất không?

Có, khi mọi cạnh đều tính như nhau: lần đầu BFS tới một đỉnh, nó đã dùng ít cạnh nhất có thể. Với các cạnh có độ dài khác nhau, hãy dùng thuật toán Dijkstra.

BFS và DFS khác nhau thế nào?

Tìm kiếm theo chiều rộng dùng hàng đợi và lan ra đều theo từng vòng. Tìm kiếm theo chiều sâu dùng ngăn xếp (hoặc đệ quy) và đi theo một đường sâu hết mức trước khi quay lui. BFS tìm được đường đi ngắn nhất theo số cạnh; DFS thì không, nhưng nó tiện để tìm chu trình và sắp xếp tô pô.

Tìm kiếm theo chiều rộng nhanh đến mức nào?

Thuật toán lấy mỗi đỉnh ra khỏi hàng đợi một lần và xét mỗi cạnh từ cả hai đầu, nên khối lượng công việc tăng theo số đỉnh cộng số cạnh.

Đồ thị của tôi có bị gửi đi đâu không?

Không. Đồ thị được tạo và tìm kiếm ngay trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Tới trình chỉnh sửa