THU T TOÁN LOANGẬ
-----------------
I) Đ T V N Đ :Ặ Ấ Ề
Thu t toán Loang th c ch t là thu t toán ậ ự ấ ậ tìm ki m theo chi u r ngế ề ộ trên đ th (Breadthồ ị
First Search). Đ hi u rõ b n ch t c a thu t toán này, ta xét bài toán ‘Thăm các đ nh c aể ể ả ấ ủ ậ ỉ ủ
m t đ th ’ nh sau: Cho m t đ th vô h ng G = (V,E), N đ nh và M c nh (s hi u c aộ ồ ị ư ộ ồ ị ướ ỉ ạ ố ệ ủ
các đ nh là 1,2,…,N). Bây gi ta đ a ra th t duy t các đ nh c a đ th đã cho theo thu tỉ ờ ư ứ ự ệ ỉ ủ ồ ị ậ
toán tìm ki m theo chi u r ng; th t duy t có th b t đ u t m t đ nh v nào đó. T t ngế ề ộ ứ ự ệ ể ắ ầ ừ ộ ỉ ư ưở
c a thu t toán là s d ng c u trúc d li u ki u hàng đ i (QUEUE - vào tr c ra tr c).ủ ậ ử ụ ấ ữ ệ ể ợ ướ ướ
Ph n t đ c n p vào đ u tiên c a QUEUE là đ nh v. Sau đó c m i đ nh p l y ra kh iầ ử ượ ạ ầ ủ ỉ ứ ỗ ỉ ấ ỏ
QUEUE là ta thăm đ nh đó đ ng th i n p vào QUEUE nh ng đ nh chung c nh v i p (chỉ ồ ờ ạ ữ ỉ ạ ớ ỉ
n p vào nh ng đ nh ch a xét đ n). Quá trình trên đ c l p đi l p l i cho đ n khi nàoạ ữ ỉ ư ế ượ ặ ặ ạ ế
QUEUE r ng thì d ng.ỗ ừ
Ch ng trình mô ph ng:ươ ỏ
Ban đ u t t c các đ nh i (i = 1..n) đ u đ t c chuaxet[i] = True. N u đ nh nào xét r i ta đ tầ ấ ả ỉ ề ặ ờ ế ỉ ồ ặ
c c a đ nh đó sang tr ng thái False.ờ ủ ỉ ạ
Procedure BFS(v); Tìm ki m theo chi u r ng b t đ u t đ nh vế ề ộ ắ ầ ừ ỉ
Begin
QUEUE = ; {Kh i t o QUEUE ban đ u là r ng}ở ạ ầ ỗ
QUEUE <= v; {N p đ nh v vào QUEUE}ạ ỉ
Chuaxet[v]:=False;{Đ nh v n p vào QUEUE là đã xét r i => c c a v là False}ỉ ạ ồ ờ ủ
While QUEUE ≠ do
Begin
P <= QUEUE; {L y p t QUEUE}ấ ừ
Thăm đ nh p;ỉ
For u € Ke(p) do {Nh ng đ nh u chung c nh v i đ nh p}ữ ỉ ạ ớ ỉ
If Chuaxet(u) then {N u đ nh u ch a xét đ n}ế ỉ ư ế
Begin
QUEUE <= u; {N p u vào QUEUE}ạ
Chuaxet[u]:=False; {Đ nh u đã xét r i =>c c a u là False }ỉ ồ ờ ủ
End;
End;
End;
BEGIN {Ch ng trình chính}ươ
For v € V do Chuaxet[v]:=True;
For v € V do
If Chuaxet[v] then BFS(v);
END.
Ng i ta th ng dùng d li u ki u m ng đ bi u di n c u trúc d li u ki u hàng đ iườ ườ ữ ệ ể ả ể ể ễ ấ ữ ệ ể ợ
QUEUE và s d ng 2 bi n Dau và Cuoi đ đi u khi n vi c n p vào và l y ph n t raử ụ ế ể ề ể ệ ạ ấ ầ ử
(bi n Dau đi u khi n thao tác l y ra, bi n Cuoi đi u khi n thao tác n p vào). ế ề ể ấ ế ề ể ạ
V i bài toán trên ta s d ng m ng 1 chi u Q: Array[1..N] of Byte đ bi u di n QUEUE.ớ ử ụ ả ề ể ể ễ
Khi đó thao tác n p vào và l y ra đ c th c hi n nh sau:ạ ấ ượ ự ệ ư
FillChar(Q,SizeOf(Q),0); {Kh i t o t t c các ph n t c a Q có giá tr 0}ở ạ ấ ả ầ ử ủ ị
Dau:=1;
Cuoi:=1;
Q[cuoi]:=v; {Ban đ u n p đ nh v vào Q}ầ ạ ỉ
Đ n p thêm đ nh u nào đó vào Q ta th c hi n:ể ạ ỉ ự ệ
1
Cuoi:=Cuoi+1; {Ho c dùng l nh Inc(Cuoi)}ặ ệ
Q[Cuoi]:=u;
Đ l y m t đ nh p nào đó ra kh i Q ta th c hi n:ể ấ ộ ỉ ỏ ự ệ
P:=Q[Dau];
Inc(Dau);
L u ý:ư Ta nói l y đ nh p ra kh i hàng đ i Q là l y ra theo c ch đi u khi n ( vì bi n Dauấ ỉ ỏ ợ ấ ơ ế ề ể ế
đã tăng lên m t đ n v qua l nh Inc(Dau)); v m t v t lý thì p v n đang n m trong m ng Q.ộ ơ ị ệ ề ặ ậ ẫ ằ ả
Nh v y ta ph i hi u r ng các ph n t trong c u trúc hàng đ i Q là các ph n tư ậ ả ể ằ ầ ử ấ ợ ầ ử
Q[Dau],..,Q[Cuoi].
Ch ng trình đ y đ :ươ ầ ủ
Program Thamdinhdothi;
Uses Crt;
Const
Nmax=253;
fi='TKR_DT.INP';
Var
f:Text;
s:Char;
A:Array[1..Nmax,1..Nmax] of 0..1;{N u có c nh gi a đ nh i và đ nh j thì A[i,j]=1, ng c l i A[i,j]=0 }ế ạ ữ ỉ ỉ ượ ạ
Chuaxet:Array[1..Nmax] of Boolean;{C c a các đ nh, có tr ng thái True n u ch a xét, ng c l i False}ờ ủ ỉ ạ ế ư ượ ạ
Q:Array[1..Nmax] of Byte;{Bi u di n hàng đ i QUEUE}ể ễ ợ
N,i,dem,dau,cuoi:Byte;
Procedure Doctep;
Begin
Assign(f,fi);
Reset(f);
Readln(f,N); {N:S đ nh c a đ th }ố ỉ ủ ồ ị
For i:=1 to N-1 do
Begin
dem:=0;
While not eoln(f) do
Begin
Read(f,s);
dem:=dem+1;
If s='1' then
Begin
A[i,dem+i]:=1;
A[dem+i,i]:=1;
End;
If s='0' then
Begin
A[i,dem+i]:=0;
A[dem+i,i]:=0;
End;
End;
Readln(f);
End;
Close(f);
2
End;
Procedure BFS(v:Integer);{Tìm ki m theo chi u r ng b t đ u t đ nh v}ế ề ộ ắ ầ ừ ỉ
Var
p,u:Byte;
Begin
FillChar(Q,Sizeof(Q),0); {Kh i t o t t c các ph n t c a m ng Q đ u b ng 0}ở ạ ấ ả ầ ử ủ ả ề ằ
dau:=1;
cuoi:=1;
Q[cuoi]:=v; {N p v vao Q}ạ
Chuaxet[v]:=False;
While dau<=cuoi do {dau > cu i là Q r ng }ố ỗ
Begin
p:=Q[dau];
dau:=dau+1; {L y đ nh p ra kh i Q }ấ ỉ ỏ
If (dau-1) mod 14 = 0 then Writeln(p:4) {In ra s hi u đ nh p - thao tác thăm đ nh p}ố ệ ỉ ỉ
Else Write(p:4); {trên màn hình xu t hi n m i dòng không quá 14 s }ấ ệ ỗ ố
For u:=1 to N do
If (A[p,u]=1) and (Chuaxet[u]) then
Begin
cuoi:=cuoi+1;
Q[cuoi]:=u;
Chuaxet[u]:=False;
End;
End;
End;
BEGIN
Clrscr;
FillChar(A,Sizeof(A),0); {Kh i t o t t c các ph n t c a m ng A đ u b ng 0}ở ạ ấ ả ầ ử ủ ả ề ằ
Doctep;
FillChar(Chuaxet,Sizeof(Chuaxet),True); {Kh i t o c c a t t c các đ nh đ u tr ng thái True - Tr ngở ạ ờ ủ ấ ả ỉ ề ở ạ ạ
thái ch a xét}ư
Writeln('Thu tu tham cac dinh cua do thi khi tim kiem theo chieu rong la:');
For i:=1 to N do
If Chuaxet[i] then BFS(i);
Writeln;
Readln;
END.
Ch ng trình trên th c hi n v i d li u vào là t p TKR_DT.INP có c u trúc:ươ ự ệ ớ ữ ệ ệ ấ
- Dòng đ u tiên, đ c g i là dòng 0: ghi các s nguyên d ng N, x cách nhau ít nh t làầ ượ ọ ố ươ ấ
m t ký t tr ng (N: S đ nh c a đ th ; x: Đ nh xu t phát);ộ ự ố ố ỉ ủ ồ ị ỉ ấ
- Trong các dòng ti p theo: Dòng th i (i = 1..N-1) ghi N-i s 0 và 1 liên ti p nhau choế ứ ố ế
bi t gi a đ nh i và đ nh j có c nh n i v i nhau hay không (j = i + 1..N). N u s ghi v trí j-ế ữ ỉ ỉ ạ ố ớ ế ố ở ị
i tính t trái sang ph i trên dòng th i có giá tr 1 thì có c nh n i gi a đ nh i và đ nh j, n u làừ ả ứ ị ạ ố ữ ỉ ỉ ế
giá tr 0 thì không có c nh n i.ị ạ ố
Ví d v i t p TKR_DT.INP sau đây:ụ ớ ệ
13 1
101000000010
01000000000
0001000000
011000000
10110000
3
1000001
000000
10000
0000
110
10
0
V i t p d li u vào nh trên ta ph i hi u nh sau:ớ ệ ữ ệ ư ả ể ư
+ dòng 0: N=13, x=1;Ở
+ dòng 1: 101000000010Ở
- gi a đ nh 1 v i đ nh 2 có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
- gi a đ nh 1 v i đ nh 3 không có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
- gi a đ nh 1 v i đ nh 4 có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
- gi a đ nh 1 v i đ nh 5 không có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
....
- gi a đ nh 1 v i đ nh 11 không có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
- gi a đ nh 1 v i đ nh 12 có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
- gi a đ nh 1 v i đ nh 13 không có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
+ dòng 2: 01000000000Ở
- gi a đ nh 2 v i đ nh 3 không có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
- gi a đ nh 2 v i đ nh 4 có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
....
+ dòng 11: 10Ở
- gi a đ nh 11 v i đ nh 12 có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
- gi a đ nh 11 v i đ nh 13 không có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
+ dòng 12: 0Ở
- gi a đ nh 12 v i đ nh 13 không có c nh n i v i nhauữ ỉ ớ ỉ ạ ố ớ
Quan h gi a các đ nh đ c mô t qua đ th sau:ệ ữ ỉ ượ ả ồ ị
2 3 5
7 8
4
1 6 9
12 13
10 11
Th t các đ nh đ c n p vào hàng đ i Q và l y ra tu n t nh sau:ứ ự ỉ ượ ạ ợ ấ ầ ự ư
Các ph n tầ ử
n p vào QạCác ph n tầ ử
có tr ng tháiạ
c là Falseờ
Các ph n tầ ử
trong Q
Ph n tầ ử
l y ra kh iấ ỏ
Q
1 1 1
2,4,12 (Khi l y 1 ra)ấ2,4,12 2,4,12 1
Không n p ph n t nàoạ ầ ử
khi l y 2 ra kh i Qấ ỏ 4,12 2
6,7 6,7 12,6,7 4
10,11 10,11 6,7,10,11 12
5,13 5,13 7,10,11,5,13 6
3 3 10,11,5,13,3 7
4
Không n p ph n t nàoạ ầ ử
khi l y 10 ra kh i Qấ ỏ 11,5,13,3 10
Không n p ph n t nàoạ ầ ử
khi l y 11 ra kh i Qấ ỏ 5,13,3 11
8,9 8,9 13,3,8,9 5
Không n p ph n t nàoạ ầ ử
khi l y 13 ra kh i Qấ ỏ 3,8,9 13
Không n p ph n t nàoạ ầ ử
khi l y 3 ra kh i Qấ ỏ 8,9 3
Không n p ph n t nàoạ ầ ử
khi l y 8 ra kh i Qấ ỏ 9 8
Không n p ph n t nàoạ ầ ử
khi l y 9 ra kh i Qấ ỏ R ngỗ9
Các ph n t tu n t đ c l y ra kh i hàng đ i Q chính là các đ nh đ c duy t:ầ ử ầ ự ượ ấ ỏ ợ ỉ ượ ệ
1, 2, 4, 12, 6, 7, 10, 11, 5, 13, 3, 8, 9
Qua đó cho th y t m t đ nh ta thăm đ n các đ nh khác liên quan đ n nó theo chi u r ng.ấ ừ ộ ỉ ế ỉ ế ề ộ
Chính vì v y thu t toán tìm ki m theo chi u r ng đ c g i là thu t toán Loang.ậ ậ ế ề ộ ượ ọ ậ
L u ý:ư
+ V i nh ng b test d li u bé thì ta có th t o m t cách th công. Nh ng v i nh ng bớ ữ ộ ữ ệ ể ạ ộ ủ ư ớ ữ ộ
test d li u l n thì ta ph i t o b ng ch ng trình. Sau đây xin gi i thi u ch ng trình t oữ ệ ớ ả ạ ằ ươ ớ ệ ươ ạ
b test v i s l ng các đ nh c a đ th là 253:ộ ớ ố ượ ỉ ủ ồ ị
Program Taotes_baithamdinh;
Uses Crt;
Const
MN=253;
fi='TKR_DT.INP';
Var
f:Text;
Procedure Gen;
Var
i,j:Integer;
Begin
Assign(f,fi);
Rewrite(f);
Writeln(f,MN);
Randomize;
For i:=1 to MN-1 do
Begin
For j:=1 to MN-i do
Write(f,Random(2)); {Random(2) cho các giá tr ng u nhiên tù 0 đ n 1}ị ẫ ế
Writeln(f);
End;
Close(f);
End;
BEGIN
Gen;
END.
5