Thuật toán BFS

[johansen]

Mình chưa hiểu về thuật toán tìm kiếm theo chiều rộng Breadth First Search.Bạn nào rành thì giúp mình với.

- VISITED(v):=1
- Khởi tạo queue với v đã được nạp vào
- while Q không rỗng do begin
call CQDELETE(v,Q); {lấy đỉnh v ra khỏi Q}
for mỗi đỉnh w lân cận với v do
if VISITED(w):=0 then begin
call CQINSERRT (w,Q);
end;
end;
- return

[kidkid]

Á à. Cái này thì cậu phải hiểu nó đã, còn chuyện code thì bàn sau:

Đầu tiên cậu đưa 1 thèng vào Queue (Q).
Trong khi Q không rỗng.
Lấy Trong Q ra 1 thèng k.hiệu v.
Tìm tất cả các phần tử có thể có từ v. Đưa vào queue

Khi Q rỗng thì cũng là lúc BFS hoàn thành.

Về nguyên tắc thì cậu coi BFS như 1 cây. Đầu tiên đưa ROOT vào, lấy tất cả các phần tử liên thông với ROOT. Trong mỗi phần tử đó lại xem nó như ROOT và tiếp tục.

Code thì xem sách hoặc tớ sẽ gởi sau.

[rox_rook]

Bạn coi bằng hình thì sẽ dễ hiểu hơn :

Đầu tiên từ đỉnh gốc có mày đen, nó sẽ bắt đầu xét lên đến các đỉnh con, cứ thế cho đến khi không còn đỉnh nào để xét nữa. Và vì sao nó liên hệ đến hàng đợi thì bạn xem hình sau :

Nó để dỉnh đầu vào queue rồi đấy.

Để ý cái màu đen là đỉnh của đồ thị mà nó đã đi qua.

Đế ý cái queue bên phải.

Cứ qua một level sẽ có lượt được đưa vào queue

Chắc bạn thấy nó vận hành thế nào rồi chứ gì ^^!




lúc này bạn thấy không, các đĩnh đã được xét hết, queue cũng sạch ^^ ! xong rùi đó.
Chú ý hình trên, các số là đánh dấu từng level của nó, cứ hình dung như cái cây có cắt nhánh con thế, và chữ cái chính là tên của mỗi đỉnh con đó thôi.
Các cạnh chính là có đường liên thông giữa 2 đỉnh đó, nếu không có cạnh tức là không có đường !
Bạn tham khảo cái này, mình copy từ chuyên đề đồ thị của tác giả Lê Minh Hoàn đó, rất dễ hiểu.
Cơ sở của phương pháp cài đặt này là lập lịch duyệt các đỉnh. Việc thăm 1 đỉnh sẽ lên lịch duyệt các đỉnh kề nó sao cho thứ tự duyệt là ưu tiên chiều rộng.( Đỉnh nào gần S hơn sẽ được duyệt trước ) ví dụ : bắt đầu ta thăm đỉnh S. Việc thăm đỉnh S sẽ phát sinh ra thứ tự duyệt các đỉnh kề sách ( ở hình trên là r, w ) –những đỉnh gần S nhất. Khi thăm đỉnh r hoặc w lại phát sinh ra các đỉnh con của chúng nữa…Nhưng thứ tự là từ trái qua phải.
Giả sử ta có 1 danh sách chứa những đỉnh đang chờ thăm. Tại mỗi bước, ta thăm đỉnh đầu danh sách và cho những đỉnh chưa xếp hàng kề với nó xếp hàng thêm vào cuối danh sách. Chính cũng vì nguyên tắc này nên danh sách chưa các đỉnh đang chờ sẽ được tổ chức dưới dạng hành đợi ( Queue )
Nếu ta có Queue là 1 hàng đợi với thủ tục Push ( v) để đẩy 1 đỉnh v vào hàng đợi và hàm Pop trả về 1 đỉnh lấy ra từ hàng đợi thì mã giả có thể viết như sau :

Với mọi đỉnh v thuộc đồ thị Free[v] = true;
Free[S] = False; /*Khởi tao ban đầu chỉ có 1 đỉnh S bị đánh dấu*/
Queue = rỗng; Push(S); /* Khởi tạo hàng đợi ban đầu chỉ có 1 đỉnh S*/
Do ( lập cho tới khi hàng đợi rỗng )
u = Pop ( Lấy hàng đợi ra 1 đỉnh u )
for ( với mọi v thuộc V )
if ( Free[v] = true và (u,v) thuộc đồ thị )
Trace[v] = u; /*lưu vết đường đi*/
Free[v] = False; /*Đánh dấu đã thăm đỉnh v*/
Push(v); /*Đẩy v vào hàng đợi*/
While ( Queue = rỗng )

[johansen]

#include "stdafx.h"#include "stdio.h"#include "memory.h"#include "conio.h"#define MaxV 20 //Define su dung cho so dinh cuc dai cua do thiint A[MaxV][MaxV]; //Ma tran keint V = 0; //So dinh cua do thiint ChuaXet[MaxV]; //Thu tuc nhap matran ke bang ban phim.void NhapMTKe(int A[][MaxV], int &V){printf("Nhap V:");scanf("%d", &V);for (int i=0; i<V; i++){for (int j=0; j<V; j++){printf("A[%d,%d] = ", i+1, j+1);scanf("%d", &(A[i][j]));}}}void XuatMTKe(int A[][MaxV], int V){printf("\nMa tran ke:\n");for (int i=0; i<V; i++){for (int j=0; j<V; j++)printf("%3d ", A[i][j]);printf("\n");}}int DocMTKe(char *fileName, int A[][MaxV], int &V){FILE *f = fopen(fileName, "rt");if (f == NULL){printf("Doc file loi !!!");return 0;} fscanf(f, "%d", &V);for (int i=0; i<V; i++){for (int j=0; j<V; j++){fscanf(f, "%d", &(A[i][j]));}}return 1;} /*Thu tuc duyet BFS, duyet theo chieu rong su dung QUEUE de chay khong de quy.*/void BFS0DeQuy(int v){int QUEUE[MaxV], topQ=0, bottomQ=0; //Khoi dau voi mot QUEUE rongQUEUE[topQ++] = v; //Dua dinh v vao QUEUE, xem no nhu la da xetChuaXet[v] = 1;while ( bottomQ < topQ ) //Lap trong khi QUEUE khac rong{v = QUEUE[bottomQ++]; //Lay dinh v tu day cua QUEUEfor (int u=0; u<V; u++)if ( A[v][u] != 0 ) //The hien u ke voi dinh vif ( ChuaXet[u]==0 ){QUEUE[topQ++] = u; // Dua u vao dinh cua QUEUEChuaXet[u] = 1;}}}*/ int main(int argc, char* argv[]){int j;NhapMTKe(A, V);//DocMTKe("D:\\Dothi_1.txt", A, V); XuatMTKe(A,V);memset(ChuaXet, 0, sizeof(ChuaXet) );DFS0DeQuy(0);printf( "Cac dinh da duyet: " );for(j=0;j<V;j++)if (ChuaXet[j] == 1)printf( "%d ", j+1 );getch ( );return 1;}

Ai giúp mình với. Sao mình dùng code này mà chương trình ko chạy vậy??

[quachtinh12]

ai giúp mình nhé.Mình đang cần code để vẽ cây nhi phân ra man hình