[myhanh]

CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG
Tìm kiếm theo chiều rộng BFS(Bread First Search)
Ý tưởng: Bắt đầu từ một đỉnh v0 nào đó của đồ thị. Quá trình tìm kiếm tại một đỉnh v nào đó diễn ra như sau: Ta đi từ đỉnh v -->w kề nó ( có trong danh sách kề ). Sau đó lập lại quá trình đi đó đến từng đỉnh trong danh sách kề và cứ tiếp tục cho đến khi không còn đi được nữa.

PROCEDURE BFS(v)
{ Tìm kiếm theo chiều rộng bắt đầu từ v, các biến chuaxet, ke là biến toàn cục }
BEGIN
   Queue:=0;
   Queue <= v;
  chuaxet[v]:=false;
  WHILE Queue <> 0 DO
   BEGIN
     p<=Queue;
     Thamdinh(p);
    FOR u in ke(p) DO
       IF chuaxet[u] THEN
         BEGIN
            Queue <=u;
            chuaxet[u]:=false;
        END;
    END;
 END;
 BEGIN
   FOR v in V DO chuaxet[v]:=true;
   FOR v in V DO
    IF chuaxet[v] THEN BFS(v);
END.