, .
:
1
, : 1, 0, 2, 3, 4, 9, 5, 8, 6, 7. , , .
( ), , , . BFS.
. 5. BFS . 4.
. v w BFS v w.
, 1 8 3, : 1- 0 - 9 - 8. , . 1, 1 8 1 2 5 8, , 3.
BFS .
. 6. .4.
. , (FIFO queue First In First Out). , .
( TurboPascal)
TurboPascal , , , . 4.
C[i, j], C[i, j] = 1 i j, C[i,j] = 0 .
Q[i], . Un , Uk . (setQueue), (getQueue), (initQueue). .
Procedure setQueue (v: integer);
Begin
Inc(Uk); Q[Uk]:=v;
End;
Procedure getQueue (var v: integer);
Begin
v:=Q[Un]; Inc(Un);
End;
Procedure initQueue;
Begin
Uk:=0; Un:=0;
End;
, , . , . Visit [i], , (, true , false ).
|
|
program Poisk_v_shirinu;
const n=9; { }
{ }
C: array [0..n,0..n] of 0..1=((0,1,0,0,0,0,0,0,0,1),
(1,0,1,1,1,0,0,0,0,0),
(0,1,0,0,0,1,0,0,0,0),
(0,1,0,0,1,0,0,0,0,0),
(0,1,0,1,0,0,0,0,0,0),
(0,0,1,0,0,0,0,0,1,0),
(0,0,0,0,0,0,0,0,1,0),
(0,0,0,0,0,0,0,0,1,0),
(0,0,0,0,0,1,1,1,0,1),
(1,0,0,0,0,0,0,0,1,0));
Visit: array [0..n] of boolean =(true,true,true,true,true,true,
true,true,true,true);
{ }
var v: integer; { }
procedure BFS(v:integer);
var Q: array [1..(n+1)] of 0..n;
{ }
Un,Uk: integer;
{ }
j: integer;
begin
Un:=0; Uk:=0; {, }
Uk:=Uk+1; Q[Uk]:=v; { }
{ }
Visit[v]:=false;
while Un < Uk do { }
begin
{ }
Un:=Un+1; v:=Q[Un];
{ }
write(v:3);
{ , v }
for j:=0 to n do
if (C[v,j]=1) and (Visit[j]) then
begin
{ , }
Uk:=Uk+1; Q[Uk]:=j;
{ }
Visit[j]:=false;
end;
end; {while}
end; {procedure}
begin
writeln(' ');
writeln ( ); readln(v);
BFS(v); { v}
end.
1: , . 4, . 8. .
2: . .
3: , .
:
1.
, , . .
. . ( , )
2 , .
v w . BFS (, ). ( ) v . .
4 . .
|
|
4 . , .
, . .
, , . ( , ).
BFS ( ).
2
1. . .
, , , . (Visual Basic, Delphi).
2. . v w. . . (Visual Basic, Delphi).
3. . BFS, . . .
(Visual Basic, Delphi).