Giáo án môn: Lý Thuyết Đồ Thị

Nguyễn Minh Đức - ĐHQG Hà Nội
24
Chng 3
CC THUT TON TèM KIM TRấN THN V NG DNG Trong lý thuyt th, cú rt nhiu thut toỏn c xõy dng da trờn c s duyt qua tt c cỏc
nh ca th sao cho mi nh ch c duyt ỳng mt ln. Do vy, vic xõy dng cỏc thut toỏn
cho phộp duyt qua tt c cỏc nh ca th mt cỏch cú h thng l mt vn quan trng thu hỳt
s quan tõm nghiờn cu ca nhiu nh khoa hc. Cỏc thut toỏn nh vy c gi chung l thut
toỏn tỡm kim trờn th.
Trong chng ny chỳng ta s nghiờn cu hai thut toỏn tỡm kim c bn trờn th l Thut
toỏn tỡm kim theo chiu sõu (Depth First Search) v Thut toỏn tỡm kim theo chiu rng (Breadth
First Search) v mt vi ng dng ca hai thut toỏn ny.
n gin cho vic trỡnh by, chỳng ta s xột th vụ hng G = (V,E), |V| = n, |E| = m;
th cú hng s c suy ra mt cỏch tng t vi mt vi im c bit cn chỳ ý.
ỏnh giỏ hiu qu ca cỏc thut toỏn ny, chỳng ta ch chỳ trng n vic ỏnh giỏ phc
tp tớnh toỏn ca thut toỏn, tc s phộp toỏn m thut toỏn cn thc hin trờn mi b d liu vo
trong trng hp xu nht. phc tp tớnh toỏn ny c biu din bng mt hm s ca kớch
thc d liu u vo. C th õy kớch thc ca d liu vo s l s nh n v s cnh m ca
th. Khi ú phc tp tớnh toỏn ca thut toỏn s c biu din bng hm hai bin f(n,m) l s
phộp toỏn nhiu nht m thut toỏn cn phi thc hin i vi mi th n nh, m cnh.
so sỏnh tc tng ca hai hm nhn giỏ tr khụng õm
f(n) v g(n) chỳng ta s dng ký hiu
f(n) = O(g(n)). iu ny cú ngha tng ng vi vic tỡm c cỏc hng s dng C v N sao
cho:

f(n
1
,n
2
, ,n
k
)

Cg(n
1
,n
2
, ,n
k
) vi
Nn

Nu phc tp tớnh toỏn ca thut toỏn l
O(g(n)) thỡ ta núi l thut toỏn cú thi gian tớnh toỏn
c
O(g(n)).
3.1 Thut toỏn tỡm kim theo chiu sõu trờn th (Depth First Search)
í tng chớnh ca thut toỏn tỡm kim theo chiu sõu cú th c hiu nh sau:
Ban u tt c cỏc nh ca th u cha c duyt n, ta s bt u vic tỡm kim t mt nh
no ú, gi s nh ú l v
1
. Sau ú chn u l mt nh (cú th chn tu ý) trong danh sỏch cỏc nh
k vi nh v
1
m cha c xột n v lp li quỏ trỡnh tỡm kim i vi nh u ny. bc tng

6
10
9
(* Tỡm kim theo chiu sõu trờn th bt u t nh v *)
(* Cỏc bin Chuaxet v Ke l bin ton cuc *)

Begin
Xet_dinh(v);
Chuaxet[v]:=False;
For u

Ke(v) do
If Chuaxet[u] Then
DFS(u);

End;
(* Chng trỡnh chớnh thc hin th tc *)

BEGIN
(* Khi to bin ton cc Chuaxet *)
For v
V do
Chuaxet[v]:=True;
(* Duyt th *)
For v
V do
If Chuaxet[v] Then
DFS(v);

END.

4:
1 9 10
Hỡnh 3.1
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

NguyÔn Minh §øc - §HQG Hµ Néi
26
1
4
3
2
5
6
7
8
9
5:
3 8
6:
7 8
7:
6 8
8:
3 5 6 7
9:
4 10
10:
4 9
Khi đó thứ tự các đỉnh được duyệt theo thuật toán trên bắt đầu từ đỉnh 1 là:


7 8
6:
5
7:
2 9
8:
6
9: Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều sâu bắt đầu từ đỉnh 1 là:

1 3 2 4 5 7 9 8 6 3.2 Thuật toán tìm kiếm theo chiều rộng trên đồ thị (Breadth First Search)
Tư tưởng chính của phương pháp tìm kiếm theo chiều rộng trên đồ thị có thể được hiểu như sau:
Ban đầu tất cả các đỉnh của đồ thị là chưa được xét đến, ta sẽ bắt đầu việc tìm kiếm từ một đỉnh
nào đó của đồ thị, giả sử đỉnh đó là v
1
. Khi duyệt đỉnh v
1
ta sẽ để ý tới tất cả các đỉnh v
11
, v
12
, , v
1k

Hình 3.2


do
Begin
p
Queue; (* Ly p ra khi Queue *)
Xet_dinh(p);
For u

Ke(p) do
If Chuaxet[u] then
Begin
Queue

u;
Chuaxet[u]:=False;
End;
End;
End;
(* Chng trỡnh chớnh thc hin th tc *)
BEGIN
(* Khi to bin ton cc Chuaxet *)
For v

V do
Chuaxet[v]:=True;
(* Duyt cỏc nh *)
For v

V do
If Chuaxet[v] then

#include<stdio.h>
#include<stdlib.h>

#define VMAX 100 //So dinh toi da cho mot do thi

typedef struct pp //Cau truc tu tro
{
int v;
struct pp *next;
}Link;

Link *Ke[VMAX]; //Danh sach ke cua do thi
int chuaxet[VMAX]; //Bien mang dung de danh dau cac dinh da xet
Link *Queue; //Hang doi luu thu tu cac dinh se xet
int n; //So dinh cua do thi
//
// Ham nhap danh sach ke cua do thi co n dinh
//
void nhap_dsk(Link *Ke[], int n)
{
int i,v;
Link *pd,*p;
//Khoi tao mang cac danh sach cac dinh ke cua cac dinh
for(i=1;i<=n;i++)
{
Ke[i] = (Link*)malloc(sizeof(Link));
Ke[i]->v=i;
Ke[i]->next = NULL;
}
//Nhap danh sach cac dinh ke cua cac dinh

// Ham hien thi danh sach ke cua do thi co n dinh
//
void in_dsk(Link *Ke[], int n)
{
int i;
Link *pd;
printf("\nDanh sach ke cua cac dinh cua do thi:\n");
printf("\n \n");
for(i=1;i<=n;i++)
{
printf("\n Danh sach cac dinh ke cua dinh %d:",Ke[i]->v);
pd = Ke[i]->next;
while(pd!=NULL)
{
printf("%5d",pd->v);
pd=pd->next;
}
}
}
//
// Ham nap mot phan tu (mot dinh ) vao hang doi
//
void Push(Link *u)
{
Link *q,*p;
q=(Link*)malloc(sizeof(Link));
q->v=u->v;
q->next=NULL;
if(Queue==NULL)
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

{
printf("%3d",u->v);
chuaxet[u->v]=0;
Link *p = Ke[u->v]->next;
while(p!=NULL)
{
if(chuaxet[p->v])
dfs(p);
p=p->next;
}
}
//
// Ham tim kiem theo chieu rong bat dau tu mot dinh
//
void bfs(Link *u)
{
Queue=NULL; //Khoi tao hang doi
Push(u);
chuaxet[u->v]=0;
while(Queue!=NULL)
{
int u;
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

NguyÔn Minh §øc - §HQG Hµ Néi
31
u=Pop();
printf("%5d",u);
Link *p=Ke[u]->next;
while(p!=NULL)

printf("\n\n ");
printf("\n\n Ban chon:"); char ch=getche();
return ch;
}
//
// Chuong trinh chinh
//
void main()
{
int kt=0,i;
char ch;
do
{
clrscr();
tieu_de();
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

NguyÔn Minh §øc - §HQG Hµ Néi
32
ch = menu();
switch(ch)
{
case '1': //Nhap danh sach ke cua do thi
clrscr();
tieu_de(); kt=1;
printf("\n\n1.Nhap danh sach ke cua do thi");
printf("\n \n\n");
printf("\n\nSo dinh cua do thi n ="); scanf("%d",&n);
nhap_dsk(Ke,n);
printf("\n\n\n\n ");

dfs(Ke[i]);
}
else
printf("\nDo thi chua duoc nhap vao!");
printf("\n\n\n\n ");
printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!");
getch();
break;
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

NguyÔn Minh §øc - §HQG Hµ Néi
33
case '4': //Tim kiem theo chieu rong tren do thi
clrscr();
tieu_de();
printf("\n\n4.Tim kiem theo chieu rong tren do thi");
printf("\n ");
if(kt)
{
//Khoi toa bien chuaxet;
for(i=1;i<=n;i++)
chuaxet[i]=1;
//Ket qua tim kiem theo chieu rong
printf("\n\nThu tu cac dinh duoc xet theo chieu rong:\n\n");
for(i=1;i<=n;i++)
if(chuaxet[i])
bfs(Ke[i]);
}
else
printf("\nDo thi chua duoc nhap vao!");

NguyÔn Minh §øc - §HQG Hµ Néi
34
1
2
3
4
5
7
6
8
Procedure DFS(u)
Begin
Chuaxet[u]:=False;
For v
∈Ke(u) do
If Chuaxet[v] then
Begin
Truoc[v]:= u;
DFS(v);
End;
End;

Thủ tục tìm kiếm theo chiều rộng áp dụng cho việc tìm đường đi:
Procedure BFS(u)
Begin
Queue : =
φ

Queue
⇐
Nếu áp dụng tìm đường đi theo thuật toán tìm kiếm theo chiều sâu bắt đầu từ đỉnh 1 ta sẽ có:
Hình 3.3
Giáo án môn: Lý Thuyết Đồ Thị

Nguyễn Minh Đức - ĐHQG Hà Nội
35
Truoc[2]=1, Truoc[3]=5, Truoc[4]=5, Truoc[5]=2, Truoc[6]=5, Truoc[7]=8, Truoc[8]=6
Vy ng i tỡm theo thut toỏn tỡm kim theo chiu sõu t nh 1 n nh 8 s l:

86521

Nu ỏp dng tỡm ng i theo thut toỏn tỡm kim theo chiu rng bt u t nh 1 ta s cú:
Truoc[2]=1, Truoc[3]=1, Truoc[4]=1, Truoc[5]=2, Truoc[6]=5, Truoc[7]=5, Truoc[8]=5
Vy ng i tỡm theo thut toỏn tỡm kim theo chiu sõu t nh 1 n nh 8 s l:

8521 Chỳ ý

Begin
Queue : =


Queue

v;
Chuaxet[u]:=False;
Thanhplt[u]:=Sotplt;
While Queue

do
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

NguyÔn Minh §øc - §HQG Hµ Néi
36
Begin
p
⇐ Queue;
For v
∈
Ke(p) do
If Chuaxet[v] then
Begin
Queue
⇐
v;
Chuaxet[v]:=False;
Thanhplt[v]:=Sotplt;
End;

struct pp *next;
}Link;
Link *Ke[VMAX]; //Danh sach ke cua do thi
int chuaxet[VMAX]; //Bien mang dung de danh dau cac dinh da xet
Link *Queue; //Hang doi dung cho thuat toan tim kiem theo chieu rong
int sTruoc[VMAX]; //Duong di tim theo thuat tim kiem theo chieu sau
int rTruoc[VMAX]; //Duong di tim theo thuat tim kiem theo chieu rong
int sotplt; //So thanh phan lien thong
int n; //So dinh cua do thi
//
// Ham nhap danh sach ke cua do thi co n dinh
//
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

NguyÔn Minh §øc - §HQG Hµ Néi
37
void nhap_dsk(Link *Ke[], int n)
{
int i,v;
Link *pd,*p;
//Khoi tao mang cac danh sach cac dinh ke cua cac dinh
for(i=1;i<=n;i++)
{
Ke[i] = (Link*)malloc(sizeof(Link));
Ke[i]->v=i;
Ke[i]->next = NULL;
}
//Nhap danh sach cac dinh ke cua cac dinh
for(i=1;i<=n;i++)
{

printf("\nDanh sach ke cua cac dinh cua do thi:\n");
printf("\n ");
for(i=1;i<=n;i++)
{
printf("\n Danh sach cac dinh ke cua dinh %d:",Ke[i]->v);
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

NguyÔn Minh §øc - §HQG Hµ Néi
38
pd = Ke[i]->next;
while(pd!=NULL)
{
printf("%5d",pd->v);
pd=pd->next;
}
}
}
//
// Ham nap mot phan tu (mot dinh ) vao hang doi
//
void Push(int t)
{
Link *q,*p;
q=(Link*)malloc(sizeof(Link));
q->v=t;
q->next=NULL;
if(Queue==NULL)
Queue = q;
else
{

NguyÔn Minh §øc - §HQG Hµ Néi
39
while(p!=NULL)
{
if(chuaxet[p->v]==1)
{
sTruoc[p->v]=u;
dfs(p->v);
}
p=p->next;
}
}
//
// Ham tim kiem theo chieu rong bat dau tu mot dinh
// ( Ap dung de tim duong di giua hai dinh va kiem tra lien thong)
//
void bfs(int t)
{
Queue=NULL; //Khoi tao hang doi
Push(t);
chuaxet[t]=sotplt;
while(Queue!=NULL)
{
int u;
u=Pop();
Link *p=Ke[u]->next;
while(p!=NULL)
{
if(chuaxet[p->v]==1)
{

{
printf("%d< ",sTruoc[j]);
j=sTruoc[j];
}
printf("%d",dau);
}
}
//
// Ham tim duong di giua hai dinh bat ky tren do thi
// Ap dung thuat toan tim kiem theo chieu rong
//
void dd_bfs()
{
int dau, cuoi;
printf("\n\nTim duong di tu dinh:"); scanf("%d",&dau);
printf("den dinh:"); scanf("%d",&cuoi);
bfs(dau);
if(chuaxet[cuoi]==1)
printf("\n\nKhong co duong di tu dinh %d den dinh %d tren do thi!",dau,cuoi);
else
{
printf("\n\nDuong di tu dinh %d den dinh %d tren do thi la:\n",dau,cuoi);
printf("%d< ",cuoi);
int j=cuoi;
while(rTruoc[j]!=dau)
{
printf("%d< ",rTruoc[j]);
j=rTruoc[j];
}
printf("%d",dau);

for(int k=1;k<=n;k++)
if(chuaxet[k]==j)
printf("%5d",k);
}
}
}
//
// Ham in tieu de cua chuong trinh
//
void tieu_de()
{
printf("\n CHUONG TRINH TIM DUONG DI VA KIEM TRA TINH LIEN THONG");
printf("\n *** \n\n");
}
//
// Ham hien thi Menu chon chuc nang cua chuong trinh
//
char menu()
{
printf("\n Menu chon chu nang");
printf("\n *** \n");
printf("\n\n 1. Nhap do thi cho boi danh sach ke");
printf("\n\n 2. Hien thi danh sach ke cua do thi");
printf("\n\n 3. Tim duong di - theo thuat tk chieu sau");
printf("\n\n 4. Tim duong di - theo thuat tk chieu rong");
printf("\n\n 5. Kiem tra tinh lien thong cua do thi");
printf("\n\n 6. Ket thuc chuong trinh");
printf("\n\n ");
printf("\n\n Ban chon:"); char ch=getche();
return ch;

case '2': //Hien thi danh sach ke cua do thi
clrscr();
tieu_de();
printf("\n\n2.In danh sach ke cua do thi");
printf("\n \n\n");
if(kt)
in_dsk(Ke,n);
else
printf("\n\nDo thi chu duoc nhap vao!");
printf("\n\n\n\n ");
printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!");
getch();
break;
case '3': //Tim duong di - theo thuat tk chieu sau
clrscr();
tieu_de();
printf("\n\n3.Tim duong di - theo thuat tk chieu sau");
printf("\n \n\n");
if(kt)
{
//Khoi toa bien chuaxet;
for(i=1;i<=n;i++)
chuaxet[i]=1;
dd_dfs();
}
else
printf("\n\nDo thi chua duoc nhap vao!");
printf("\n\n\n\n ");
printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!");
getch();

else
printf("\n\nDo thi chua duoc nhap vao!");
printf("\n\n\n\n ");
printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!");
getch();
break;
case '6': //Ket thuc chuong trinh
printf("\n\nXin cam on ban da su dung chuong trinh!");
getch();
break;
}
}while(ch!='6');
}