Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
Mở đầu
ấu trúc dữ liệu là môn học quan trọng mấu chốt trong chuyên ngành Công
nghệ thông tin. Nó là cơ sơ để chúng ta giải quyết một số bài toán đồng thời
cung cấp những hiểu biết về cách tổ chức dữ liệu nhằm giải quyết các bài
toán hiệu quả nhất.
C
Đề tài của nhóm là : mê cung và đường đi. Nội dung báo cáo chia ra 5 phần
Phần 1 : Cơ sở lý thuyết
Phần 2 : Mô tả bài toán
Phần 3 : Thuật toán
Phần 4 : Chương trình
Phần 5 : Kết quả & đánh giá
Nhóm đã cố gắng hết sức để hoàn chỉnh đồ án, song chắc chắn không tránh
khỏi thiếu sót, vì vậy kính mong nhận được góp ý và hướng dẫn của thầy cô cùng các
bạn.
Nhân dịp này, nhóm xin chân thành cám ơn các giảng viên khoa Công Nghệ
Thông Tin và đặc biệt là thầy Phan Thanh Tao đã hướng dẫn, giúp đỡ nhóm hoàn
thành Đồ án này.
Nhóm báo cáo : C15
Nguyễn Xuân Thạch : 07T3
Lê Trần Lam : 07T3
Nguyễn Văn Nam : 07T3
Lê Trung Dũng : 07T3
Đà Nẵng 27-11-2009
Mục lục
Nhóm báo cáo : C15 - Số đề tài : 14  Page 1
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
PHẦN 1: CÁC CƠ SỞ LÝ THUYẾT 3




PHẦN 2: MÔ TẢ BÀI TOÁN 5

 !"#" $%&'(
PHẦN 3: THUẬT TOÁN 7
)&!*+,-.
)&/!*0
PHẦN 4: CHƯƠNG TRÌNH 9
PHẦN 5: KẾT QUẢ & ĐÁNH GIÁ 17
1!2#345#6!789.
:9;
Giới thiệu đề tài
Đề tài : Cho một mê cung (maze) và tìm đường đi trong mê cung
Nhóm báo cáo : C15 - Số đề tài : 14  Page 2
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
PHẦN 1: CÁC CƠ SỞ LÝ THUYẾT
Mê cung:
Là một hệ thống các con đường hoặc lòng hang động. Được xây dựng nên bởi
các hàng rào được bố trí theo quy luật nào đó.
Các thành phần của mê cung:
Ô tường
Ô có thể đi
Ô bắt đầu, kết thúc
Tính chất: có duy nhất 1 lối vào và 1 lối ra. Đường đi từ lối vào đến lối ra rất phức tạp.
Ứng dụng : Xây dựng các mật đạo, các mê cung giải trí trong công viên, trò chơi điện
tử.
Thuật toán Loang :
Là thuật toán duyệt theo chiều rộng để tìm ra kết quả mà chúng ta mong muốn,
tư tưởng của thuật toán rất đơn giản : khi cho 1 bài toán chúng ta sẽ được cung cấp 1
số dữ kiện ban đầu và phải đưa ra kết quả mà bài yêu cầu(có thể có hoặc không),

phương pháp này đưa ra với mục đích duyệt mọi khả năng có thể có của bài toán và
nếu trong các khả năng đó có cấu hình mong muốn thì chúng ta coi như tìm được đáp
án và ngược lại là không có kết quả (no solution).
Nhóm báo cáo : C15 - Số đề tài : 14  Page 3
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
Để giải quyết dễ dàng người ta mô hình hóa bài toán về mô hình 1 đồ thị để làm việc
Giả sử dữ liệu ban đầu là gốc (root) của cây thì các khả năng sẽ là các lá, và
trình tự giải bài toán sẽ là đường đi từ root đến lá (nếu lá đó là cấu hình mong muốn).
quá trình Loang là quá trình kiểm tra tất cả các đường đi từ gốc đến tất cả các lá nếu
tìm được đường đi đưa ra đáp án mà bài yêu cầu thì bài toán coi như giải xong.
Cấu trúc hàng đợi:
Hàng đợi (tiếng Anh: queue) là một cấu trúc dữ liệu dùng để chứa các đối
tượng làm việc theo cơ chế FIFO (viết tắc từ tiếng Anh: First In First Out), nghĩa là
việc thêm vào hoặc lấy một đối tượng ra khỏi hàng đợi, được thực hiện theo cơ chế
"vào trước ra trước".
Trong hàng đợi, các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào,
nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi. Thao
tác thêm vào và lấy một đối tượng ra khỏi hàng đợi được gọi lần lượt là "enqueue" và
"dequeue". Việc thêm một đối tượng luôn diễn ra ở cuối hàng đợi và một phần tử luôn
được lấy ra từ đầu hàng đợi.
Nhóm báo cáo : C15 - Số đề tài : 14  Page 4
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
Cấu trúc dữ liệu hàng đợi có thể định nghĩa như sau: Hàng đợi là một cấu trúc
dữ liệu tương tự như ngăn xếp, hàng đợi hỗ trợ các thao tác:
 EnQueue(o): thêm đối tượng o vào cuối hàng đợi.
 DeQueue(): lấy đối tượng ở đầu queue ra khỏi hàng đợi và trả về giá trị của nó.
Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.
Các thao tác thêm, trích và huỷ một phần tử phải được thực hiện ở hai phía
khác nhau của hàng đợi, do đó hoạt động của hàng đợi được thực hiện theo cơ chế
FIFO. Cũng như ngăn xếp, cấu trúc mảng một chiều hoặc cấu trúc danh sách liên kết

có thể dùng để biểu diễn cấu trúc hàng đợi.
Khi mô hình bài toán về đồ thị để làm việc thì việc quan trọng hàng đầu là phải
xác định được cấu trúc (struct) của định và quan hệ giữa các đỉnh. khi xác định xong
thì chúng ta tiến hành Loang bình thường, khi đó cấu trúc phần tử (element) của
Queue chính là cấu trúc của đỉnh.
Trong tin học, cấu trúc dữ liệu hàng đợi có nhiều ứng dụng: khử đệ qui, tổ chức
lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui, vét cạn, tổ chức quản lý và
phân phối tiến trình trong các hệ điều hành,
PHẦN 2: MÔ TẢ BÀI TOÁN
Yêu cầu bài toán:
Với một mê cung cho trước, hãy tìm đường đi trong mê cung. Ta cụ thể bài
toán như sau:
Biểu diễn mê cung bằng ma trận 2 chiều với các giá trị 1 là tường , 0 là đường
đi. Ta nhập vào ma trận và xuất ra đường đi tương ứng với ma trận mê cung đó.
1. Thông tin vào :
a. Ma trận mê cung
b. Toạ độ vào, toạ độ ra
c. Hình minh hoạ
Nhóm báo cáo : C15 - Số đề tài : 14  Page 5
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
1 0 1 1 1 1 1 1 1 1
1 0 1 0 0 0 0 0 0 1
1 0 0 0 1 1 0 1 1 1
1 1 0 0 0 1 0 0 0 1
1 1 0 1 0 0 1 1 0 1
1 0 0 1 1 0 1 1 0 1
1 1 0 1 0 0 0 0 0 1
1 1 0 0 0 1 1 1 0 1
1 0 0 1 0 0 0 0 0 1
1 1 1 1 1 1 1 1 0 1

2. Thông tin ra
a. Đường ngắn nhất để thoát khỏi mê cung
b. Tất cả các đường có thể thoát khỏi mê cung
c. Hình minh hoạ

Cấu trúc lưu trữ dữ liệu và các hàm chính:
Để giải quyết bài toán đã cho, ta dùng cấu trúc hàng đợi. Cấu trúc được mô tả
bằng đoạn mã sau( trong ngôn ngữ C++) :
typedef struct tagDNode
{
int x;
int y;
struct tagDNode* next;
struct tagDNode* father;
}DNODE;
• x,y là toạ độ hiện hành
• next là con trỏ trỏ đến phần từ ngay sau nó
• father là con trỏ trỏ đến phần tử đã dẫn tới nó
Hình minh hoạ
Nhóm báo cáo : C15 - Số đề tài : 14  Page 6
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
typedef struct tagDList
{
DNODE* pHead;
DNODE* pTail;
}QUEUE;
Hinh minh hoạ
Các nguyên mẫu hàm và công dụng của nó
 DNODE* GetNode(int u,int v); //khởi tạo 1 phần tử kiểu tagDNode và giá trị
trả về là con //trỏ kiểu DNODE để quản lý nó

 void EnQueue(QUEUE &l,DNODE* newe); //Thêm 1 phần tử newe vào
hàng đợi l
 DNODE* DeQueue(QUEUE &l); //Lấy 1 phần tử ra khỏi hàng đợi ( theo cơ
chế vào trước /ra trước )
PHẦN 3: THUẬT TOÁN
Thuật toán tìm đường đi (ngắn nhất):
QUEUE maze;
DNODE* p, g;
Bước 1:
Nạp đỉnh vào vào hàng đợi
• p=GetNode(xstart, ystart);
• EnQueue(maze,p);
Bước 2 :
While(maze.pHead != NULL)// Lặp trong khi hàng đợi chưa rỗng
{
- p=DeQueue(maze)// Lấy 1 đỉnh từ hàng đợi để xét
Nhóm báo cáo : C15 - Số đề tài : 14  Page 7
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
- Kiểm tra đỉnh đó là đỉnh ra ?
o Nếu đúng :In kết quả, kết thúc thuật toán
o Nếu sai :
 Kiểm tra các hướng có thể đi từ đỉnh đó ? ( cụ thể là trái phải
trên dưới)
• Nếu đi được :
o g=GetNode(xnew,ynew);
o EnQueue(maze,g);// Nạp đỉnh mới vào hàng đợi
o g->father=p;// Đánh dấu đỉnh dẫn tới g
}
Nếu kết thúc vòng lặp mà vẫn chưa có kết quả thì thông báo vô nghiệm.
Thuật toán tìm tất cả các đường đi:

DNODE* S, Sw; //S là stack chứa các phần tử chứa đỉnh tạo thành đường đi
//Sw là stack chứa các đỉnh tạm thời
//S là stack chứa các đỉnh tạo thành đường đi
Bước 1:
Nạp đỉnh vào vào stack S
Bước 2:
Xét đỉnh đầu tiên ở S
- Nếu có đường đi từ đỉnh đó
{
Nạp tất cả đỉnh g đi được vào Sw;
Đánh dấu tất cả g->father=S;
Nạp đỉnh đầu của Sw vào S;
Xoá đỉnh đầu tiên của Sw;
Lặp lại bước 2:
}
- Nếu như không thể đi được nữa (bị tắt đường)
{
Nếu như Sw = NULL thì kết thúc
Nếu không
{
Xoá lùi các đỉnh trong S cho tới vị trí Sw->father;// nghĩa là tại
đỉnh mà ở đó có ngã rẽ
Nạp đỉnh đầu của Sw vào S;
Xoá đỉnh đầu của Sw;
Lặp lại bước 2:
Nhóm báo cáo : C15 - Số đề tài : 14  Page 8
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
}
}
- Nếu đỉnh hiện tại là đỉnh ra

{
Xuất kết quả (nghĩa là xuất các đỉnh trong S);
Nếu Sw = NULL thì kết thúc
Nếu không
{
Xoá lùi trong S tới vị trí Sw->father;
Nạp đỉnh đầu của Sw vào S;
Xoá đỉnh đầu của Sw;
Lặp lại bước 2:
}
}
PHẦN 4: CHƯƠNG TRÌNH
Vì chương trình được viết bằng ngôn ngữ Visual C++ bao gồm nhiều thư viện
tạo form, dialog nên chúng ta chỉ trình bày đoạn chương trình C++ trong môi trường
Borland C.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int MAZE[20][20]; // mang luu ma tran chinh
int MAZE2[20][20]; // mang luu ma tran phu
int hang,cot,xstart,ystart,xgoal,ygoal;
int leftDraw, topDraw; // toa do bat dau ve me cung
int coutWay;
typedef struct tagDNode
{
int x;
int y;
struct tagDNode* next;
struct tagDNode* father;
}DNODE;

typedef struct tagDList//tagDList la cau truc gom 2 con tro DNODE
//con tro DNODE co cau truc tagDNode
{
Nhóm báo cáo : C15 - Số đề tài : 14  Page 9
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
DNODE* pHead;
DNODE* pTail;
}QUEUE;
DNODE* GetNode(int u,int v)//Ham khoi tao,kieu tra ve la con tro DNODE tro den
//1 phan tu tagDNode[DNODE]
{
DNODE *p;//p la con tro tro den DNODE
p=new DNODE;
if(p==NULL)
{
printf("Het bo nho");
exit(1);
}
//Gan thong tin cho p;
p->x=u;
p->y=v;
p->next=NULL;
p->father=NULL;
return p;
}
void AddFirst(QUEUE &l,DNODE* new_ele)//new_ele la con tro
{
if(l.pHead==NULL)//Xau rong
{
l.pHead=new_ele;

l.pTail=l.pHead;
}
else
{
new_ele->next=l.pHead;
l.pHead=new_ele;
}
}
void AddLast(QUEUE &l,DNODE* newe)//Right!!
{
if(l.pHead==NULL)//xau rong~
{
l.pHead=newe;
Nhóm báo cáo : C15 - Số đề tài : 14  Page 10
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
l.pTail=l.pHead;
}
else
{
l.pTail->next=newe;
l.pTail=newe;
}
}
DNODE* RemoveFirst(QUEUE &l)//lay ra phan tu dau tien,ko xoa !
{
DNODE *p;
p=NULL;
if(l.pHead!=NULL)//xau ko rong~
{
p=l.pHead;

l.pHead=l.pHead->next;
if(l.pHead==NULL) l.pTail=NULL;
}
return p;
}
int check(int x,int y)
{
if(x<0||y<0) return 0;
if(x>=hang||y>=cot) return 0;
if(MAZE2[x][y]==0) return 1;
else return 0;
}
//////////////////////////////////////////////////////////////////////////
//Khoi Tao Tim All Way
FILE* fp;
int demA;
void WriteFile(DNODE* l)
{
DNODE* p;
p=l;
//fp=fopen("ketqua.txt","a+");
fprintf(fp,"%d ",demA);
Nhóm báo cáo : C15 - Số đề tài : 14  Page 11
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
while(p!=NULL)
{
fprintf(fp,"%d %d ",p->x,p->y);
p=p->next;
}
fprintf(fp,"\n\n");

}
void DisplayStack(DNODE* l)//Right!!
{
DNODE* p;
p=l;
printf("\n");
while(p!=NULL)
{
printf("%d%d-",p->x,p->y);
p=p->next;demA++;
}
printf("\n");
}
void SetFree(DNODE* &l,DNODE* vitri)//Right!!!
{
DNODE* p;int x,y;//Ham se xoa tu "Dinh Stack" den "vitri" cho truoc
if(l==NULL) return;
else
{
while(1)
{
if(l==vitri) return;
p=l;
l=l->next;
x=p->x;y=p->y;MAZE2[x][y]=0;
delete p;
}
}
}
void AddS(DNODE* &l,DNODE* new_ele)//Right!!!

{
int x,y;
new_ele->next=l;
Nhóm báo cáo : C15 - Số đề tài : 14  Page 12
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
l=new_ele;
x=new_ele->x;y=new_ele->y;
MAZE2[x][y]=100;//chu y khi add vao "duong di" thi khong cho di wa nua,dah
dau 100
}
void AddSw(DNODE* &l,DNODE* new_ele)//Right!!!
{
new_ele->next=l;
l=new_ele; //Ham nay chi add vao Stack wait nen ko can thiet danh dau 100
} //nghia la co the add them vao Stack wait 1 lan nua
void DelSw(DNODE* &l)//Right!!!
{
l=l->next; //Thuc chat ham DelSw chi la dich con tro Stack den ptu tiep theo
//Khong xoa,vi "Stack dau" can de Add vao "duong di"
}
void DelS(DNODE* &l)
{
DNODE* p;int x,y;
if(l!=NULL){
p=l;
x=p->x;y=p->y;MAZE2[x][y]=0;
l=l->next;
delete p;
} //Ham xoa dinh stack, thuat toan ko dung ham nay
}

void AllWay(int daux,int dauy,int duoix,int duoiy)
{
DNODE* S,*p,*g,*Sw;
int x,y,beAdd;
S=NULL;
Sw=NULL;
p=GetNode(daux,dauy);AddS(S,p); //nap Dinh dau tien
// TIM ALL WAY
while(1)
{
x=S->x;y=S->y;//printf("\n%d:%d",x,y);
if(x==duoix&&y==duoiy)//Neu ve dich
{
Nhóm báo cáo : C15 - Số đề tài : 14  Page 13
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
DisplayStack(S);//WriteFile(S);
demA=0;
if(Sw==NULL) break; //Thuat toan se dung khi ko con ptu trong
else{ //"Stack Wait",cung co nghia la
het //duong roi
SetFree(S,Sw->father);//neu chua het duog, tiep tuc
Add //"Stack wait"
g=Sw;DelSw(Sw); //vao trong "duong di"
AddS(S,g); //chu y vi g=Sw la bien con
//tro,nen moi thay doi
} //cua g deu anh huong toi
//Sw,nen can dich Sw trc
} //khi thay doi g[AddS(S,g)]
else
{

beAdd=0;//Bien BeAdd dung de danh dau xem dinh hien tai co bi
//tat
if(check(x,y+1)==1)//duong hay khong,neu co the di duoc thi dua
{ //dua all vao Stack Wait
p=GetNode(x,y+1);p->father=S;AddSw(Sw,p);
beAdd=1;
}
if(check(x,y-1)==1)
{
p=GetNode(x,y-1);p->father=S;AddSw(Sw,p);
beAdd=1;
}
if(check(x-1,y)==1)
{
p=GetNode(x-1,y);p->father=S;AddSw(Sw,p);
beAdd=1;
}
if(check(x+1,y)==1)
{
p=GetNode(x+1,y);p->father=S;AddSw(Sw,p);
beAdd=1;
}
if(beAdd==1) //Neu nhu tai dinh hien tai co duog di,thi
ta //add
Nhóm báo cáo : C15 - Số đề tài : 14  Page 14
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
{ //Stack wait -> Stack Way
g=Sw;DelSw(Sw);
AddS(S,g);
}

else //Neu beAdd==0 nghia la tat duong,thi xoa lui
cac //duong di
{ //xoa den dinh ma noi do co the re~ sag
ptu //nam trong
if(Sw==NULL) break;//Stack Wait
else
{
SetFree(S,Sw->father);
g=Sw;DelSw(Sw);
AddS(S,g);
}
}
}//end else
}//end while
fclose(fp);
//
}
void GanMT()
{
int i,j;
for(i=0;i<hang;i++)
for(j=0;j<cot;j++) MAZE2[i][j]=MAZE[i][j];
}
//////////////////////////////////////////////////////////////////////////
void main()
{
FILE *f;
f=fopen("maze1.txt","r");
fscanf(f,"%d",&hang);
fscanf(f,"%d",&cot);

fscanf(f,"%d",&xstart);
fscanf(f,"%d",&ystart);
fscanf(f,"%d",&xgoal);
fscanf(f,"%d",&ygoal);
Nhóm báo cáo : C15 - Số đề tài : 14  Page 15
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
for(int i=0;i<hang;i++)
for(int j=0;j<cot;j++) fscanf(f,"%d",&MAZE[i][j]);
fclose(f);
for(int i=0;i<hang;i++){
for(int j=0;j<cot;j++)
printf("%3d",MAZE[i][j]);
printf("\n");
}
GanMT();
//////////////////////////////////////////////////////////////////////////
//Tim Duong Ngan Nhat
int tempx,tempy;
DNODE *p,*g;
QUEUE Q;
Q.pHead=Q.pTail=NULL;
p=GetNode(xgoal,ygoal); // Duyet nguoc tu dich den diem bat dau
// de dua vao DSLK se in ra dung thu tu
AddLast(Q,p);
while(Q.pHead!=NULL )
{
p=RemoveFirst(Q);
tempx=p->x;
tempy=p->y;
if(tempx==xstart&&tempy==ystart) {

g=p;
break;
}
if(check(tempx-1,tempy)==1){
g=GetNode(tempx-1,tempy);
g->father=p;
AddLast(Q,g);
MAZE2[tempx-1][tempy]=100;
}
if(check(tempx+1,tempy)==1)
{g=GetNode(tempx+1,tempy);g->father=p;
AddLast(Q,g);MAZE2[tempx+1][tempy]=100;}
Nhóm báo cáo : C15 - Số đề tài : 14  Page 16
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
if(check(tempx,tempy-1)==1)
{g=GetNode(tempx,tempy-1);g->father=p;
AddLast(Q,g);MAZE2[tempx][tempy-1]=100;}
if(check(tempx,tempy+1)==1)
{g=GetNode(tempx,tempy+1);g->father=p;
AddLast(Q,g);MAZE2[tempx][tempy+1]=100;}
}
if(MAZE2[xstart][ystart]==0) // Neu khong den duoc Diem Start -> ko co
//duong
{
printf("Can't find a path from Start to Goal!");
}
else{
//ve duong
int dem=0;
int i,j;

printf("\nDuong Di Ngan Nhat:\n");
while(g!=NULL) // se duyet luon NODE dau tien
{ dem++;
i=g->x;
j=g->y;
printf("%d:%d ",i,j);
g=g->father;
}
}
//////////////////////////////////////////////////////////////////////////
//Tim Tat Ca Cac Duong
GanMT();
printf("\nTat Ca Cac Duong Di:\n");
AllWay(xstart,ystart,xgoal,ygoal);
}
PHẦN 5: KẾT QUẢ & ĐÁNH GIÁ
Hướng dẫn sử dụng chương trình
Giống như các chương trình phổ biến trên window, ta click vào file .exe chương
trình có giao diện đơn giản như sau:
Nhóm báo cáo : C15 - Số đề tài : 14  Page 17
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
Mở file dữ liệu mê cung có sẵn và ta được mê cung vẽ bằng các ô vuông như
sau với tường là màu đỏ, vàng là đường đi và màu xanh là đỉnh vào và ra.
Click chọn menu Best Path, chương trình sẽ vẽ ra đường đi ngắn nhất và liệt kê
số bước đi
Nhóm báo cáo : C15 - Số đề tài : 14  Page 18
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
Sau khi Click vào menu All Path, sẽ có hộp thoại nhắc ta Click vào menu View
(hoặc phím Enter) để xem lần lượt các đường đi.
Đánh giá

Vì dùng thuật toán tìm kiếm theo chiều rộng cho nên bài toán hiệu quả khi lời
giải nằm gần gốc của cây tìm kiếm (nghĩa là đỉnh ra gần đỉnh vào). Nhưng do sử dụng
cấu trúc hàng đợi nên đã giảm đáng kể số lần tìm kiếm giải vô ích so với cách dùng
tập hợp lưu các đỉnh kế tiếp
Nhóm báo cáo : C15 - Số đề tài : 14  Page 19
Đồ án Cấu Trúc Dữ Liệu – Nhóm 12A GVHD: Phan Thanh Tao
Trường hợp xấu nhất thì bài toán sẽ vét cạn toàn bộ. Tuy nhiên thuật toán này
luôn luôn tìm ra lời giải.
Tài liệu tham khảo
Tài liệu Cấu trúc dữ liệu - Thầy Phan Chí Tùng - Đại Học Bách Khoa Đà Nẵng
vi.wikipedia.org
oo
Nhóm báo cáo : C15 - Số đề tài : 14  Page 20