Thuật toán BFS (Beadth First Search)


Đu tiên t đnh gc có mày đen, nó s bt đu xét lên đến các đnh con, c thế cho đến khi không còn đnh nào đ xét na. Và vì sao nó liên h đến hàng đi thì bn xem hình sau :

Nó đ dnh đu vào queue ri đy.

Đ ý cái màu đen là đnh ca đ th mà nó đã đi qua.

Đế ý cái queue bên phi.

C qua mt level s có lượt được đưa vào queue

Chc bn thy nó vn hành thế nào ri ch gì ^^!




lúc này bn thy không, các đĩnh đã được xét hết, queue cũng sch ^^ ! xong rùi đó.
Chú ý hình trên, các s là đánh du tng level ca nó, c hình dung như cái cây có ct nhánh con thế, và ch cái chính là tên ca mi đnh con đó thôi.
Các cnh chính là có đường liên thông gia 2 đnh đó, nếu không có cnh tc là không có đường !
Bn tham kho cái này, mình copy t chuyên đ đ th ca tác gi Lê Minh Hoàn đó, rt d hiu.
Cơ s ca phương pháp cài đt này là lp lch duyt các đnh. Vic thăm 1 đnh s lên lch duyt các đnh k nó sao cho th t duyt là ưu tiên chiu rng.( Đnh nào gn S hơn s được duyt trước ) ví d : bt đu ta thăm đnh S. Vic thăm đnh S s phát sinh ra th t duyt các đnh k sách ( hình trên là r, w ) –nhng đnh gn S nht. Khi thăm đnh r hoc w li phát sinh ra các đnh con ca chúng na…Nhưng th t là t trái qua phi.
Gi s ta có 1 danh sách cha nhng đnh đang ch thăm. Ti mi bước, ta thăm đnh đu danh sách và cho nhng đnh chưa xếp hàng k vi nó xếp hàng thêm vào cui danh sách. Chính cũng vì nguyên tc này nên danh sách chưa các đnh đang ch s được t chc dưới dng hành đi ( Queue )
Nếu ta có Queue là 1 hàng đi vi th tc Push ( v) đ đy 1 đnh v vào hàng đi và hàm Pop tr v 1 đnh ly ra t hàng đi thì mã gi có th viết như sau :

Vi mi đnh v thuc đ th Free[v] = true;
Free[S] = False; /*Khi tao ban đu ch có 1 đnh S b đánh du*/
Queue = rng; Push(S); /* Khi to hàng đi ban đu ch có 1 đnh S*/
Do ( lp cho ti khi hàng đi rng )
u = Pop ( Ly hàng đi ra 1 đnh u )
for ( vi mi v thuc V )
if ( Free[v] = true và (u,v) thuc đ th )
Trace[v] = u; /*lưu vết đường đi*/
Free[v] = False; /*Đánh du đã thăm đnh v*/
Push(v); /*Đy v vào hàng đi*/
While ( Queue = rng )

Đ xây dng gii thut trên máy tính cn làm rõ các cu trúc d liu biu din đ th cũng như quá trình xét các đnh và các cnh. Gi s đ th G cho bi các danh sách các cnh k vi tng đnh. Danh sách này thường được ký hiu là Adj[u] đi vi danh scáh các cnh k đnh u. Đ phân bit các đnh chưa nm trong T, các đnh trong T đã xét xong và chưa xét, ta hình dung mt quá trình tô màu các đnh: Đnh mi b sung vào T thì tô màu xám (GRAY), đnh trong T đã xét xong thi tô màu đen (BLACK), các đnh chưa nm trong T thi tô mu trng (WHITE). Ta còn mun xác đnh các cnh nào nm trên cây. Xem T như mt cây có gc, tr gc, mi cnh trong cây ni mt đnh vi cha ca nó, vì vy ta dùng mt hàm Parent(u) đ xác đnh các cnh được đưa vào cây T. Vì thế, khi khi to ta có các biến danh sách COLOR(u) và PARENTS(u). Theo nguyên tc xét đnh gn gc nht, các đnh gia nhp cây sm s được xét trươc. Đ “theo dõi” cht ch th t các đnh được đưa vào T ta dùng mt cu trúc hàng đi Q (Queue).

Procedure BFS(G,r) {

Var
list COLOR(u),PARENTS(u),Queue Q

/* Khởi tạo */


For each u of E do {

GRAY(u)=WHITE

PARENTS(u)=Null

}


Push(Q,r) /*Đẩy đỉnh đầu tiên vào hàng đợi*/

 

/*Xét các đỉnh*/


While Q <> rỗng do {

u = Pop(Q);/*Lấy đỉnh đầu hàng đợi Q ra để xét*/

COLOR(s)=GRAY


For each v of Adj(u)

{


if COLOR(v)=WHITE then {

COLOR(v)=GRAY

PARENTS(v)=u


Push(Q,v) /*đẩy đỉnh v vào hàng đợi*/

}

COLOR(u)=BLACK

}

}


Return PARENTS


 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: