BFS (breadth first search)

Đỉnh xuất phát ở đây cũng được thăm đầu tiên,nhưng có khác với DFS là ở chỗ đỉnh được thăm càng muộn sẽ sớm trở thành đỉnh đã duyệt xong. Điều này là tất yếu bởi việc chúng ta thay việc sử dụng Stack bằng việc dùng Queue. Có thể nói tư tưởng của thuật toán là sử dụng một hàng đợi. Đỉnh được thăm sẽ xếp hàng trong hàng đợi này. Nó chỉ ra khỏi hàng đợi khi không còn đỉnh liền kề với nó mà lại chưa được thăm. Công việc sẽ kết thúc khi Queue trở nên rỗng. Tương tự thuật toán DFS chúng ta cũng sử dụng hàm tìm đỉnh liền kề, hai mảng was_visited[20]daTham[20], hai biến start, soDinh với tác dụng tương tự.

Thuật toán như sau:

if(start<soDinh){

daTham[0]=start; //ghi nhận đỉnh đầu tiên được thăm

theQueue.Add(start); //đưa đỉnh đó vào queue

was_visited[start]=true; //đánh dấu đỉnh được thăm

int t = 0;

while(!theQueue.is_empty()){

dinhQueue = theQueue.giaTriDauQueue();//tìm đến đỉnh đầu qeue

int k = dinhLienKe(dinhQueue,t);

if(k==-2){ //nếu không có đỉnh liền kề, k =-2

——theQueue.eliminate(dinhQueue);//lấy ra đỉnh đầu queue

——t = 0;

}

else{

——was_visited[k] = true;// đánh dấu đỉnh liền kề của v đã được thăm

——if(k<soDinh-1)

———t = k+1; //sẽ duyệt từ đỉnh thứ k+1

——else t = k; //khi k=siDinh thì không duyệt thêm

——theQueue.Add(k);// đưa đỉnh liền kề vào queue

——daTham[++stt] = k;//đưa đỉnh liền kề vào mảng đã thăm theo thứ tự    }

}

}

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s