Tìm kiếm theo chiều rộng trên đồ thị

Để ý rằng trong thuật toán tìm kiếm theo chiều sâu đỉnh được thăm càng muộn sẽ càng sớm trở thành đã duyệt xong. Điều đó là hệ quả tất yếu của việc các đỉnh được thăm sẽ được kết nạp vào trong ngăn xếp (STACK). , nếu nói một cách ngắn gọn, được xây dựng trên cơ sở thay thế ngăn xếp (STACK) bởi hàng đợi (QUEUE). Với sự cải biên như vậy, đỉnh được thăm càng sớm sẽ càng sớm trở thành đã duyệt xong (tức là càng sớm dời khỏi hàng đợi). Một đỉnh sẽ trở thành đã duyệt xong ngay sau khi ta xét xong tất cả các đỉnh kề (chưa được thăm) với nó. Thủ tục có thể mô tả như sau:

Procedure BFS(v);

(*Tim kiem theo chieu rong bat dau tu dinh v, cac bien Chuaxet, Ke la bien cuc bo*)

begin

QUEUE:= ∅ ;

QUEUE ⇐ v; (*ket qua nap vao QUEUE*)

Chuaxet[v]:=false;

While QUEUE<> ∅ do

Begin

p ⇐ QUEUE:; (*lay p tu QUEUE:*)

Tham_dinh(p);

For u ∈ Ke(v) do

If Chuaxet[u] them

Begin

QUEUE ⇐ u;

Chuaxet[u]:=false;

End;

End;

end;

Khi đó, tìm kiếm theo chiều rộng trên đồ thị được thực hiện nhờ thuật toán sau:

Begin

(*Initialization*)

for f ∈ V do Chuaxet[v]:=true;

for v ∈ V do

if Chuaxet[v] then BFS(v);

End.

Lập luận tương tự như trong thủ tục tìm kiếm theo chiều sâu, có thể chỉ ra được rằng lệnh gọi BFS(v) sẽ cho phép thăm đến tất cả các đỉnh thuộc cùng thành phần liên thông với đỉnh v, và mỗi đỉnh của đồ thị sẽ được thăm đúng một lần. Độ phức tạp tính toán của thuật toán là O(m+n).

Thí dụ 2. Xét đồ thị xét trong hình 1. Thứ tự thăm đỉnh của đồ thị theo thuật toán tìm kiếm theo chiều rộng được ghi trong ngoặc.

Hình3. Chỉ số mới (trong ngoặc) của các đỉnh được đánh lại theo thứ tự chúng được thăm trong thuật toán tìm kiếm theo chiều sâu.