. 1.
:
1
, : 1, 0, 9, 8, 5, 2, 6, 7, 3, 4.
. 1 , , . . , , .
, - , , .
( ).
. 2 DFS ,
. 1
DFS .
. 3 .1
. , (LIFO queue Last In First Out). . , .
( TurboPascal)
DFS.
C[i, j], C[i, j] = 1 i j, C[i,j] = 0 .
. - .
TurboPascal Stek[i], . Uk . (setStek), (getStek), (initStek). .
Procedure setStek(v: integer);
Begin
Inc(Uk); Stek[Uk]:=v;
End;
Procedure getStek(var v: integer);
Begin
v:= Stek[Uk]; Dec(Uk);
End;
Procedure initStek;
Begin
Uk:=0;
End;
, , . , . Visit [i], , (, true , false )
|
|
program Poisk_v_glubinu;
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; { }
{1 - }
procedure DFS(v:integer);
var t: integer;
begin
write(v: 3); Visit[v]:=false;
for t:=0 to n do
if (C[v,t]=1) and (Visit[t]) then
DFS(t);
end;
{2 - }
procedure DFS(v:integer);
var Stek: array [1..(n+1)] of 0..n; { }
Uk: integer; { }
t: integer; f: boolean;
begin
write(v:3);
{, }
Uk:=0;
{ }
Uk:=Uk+1; Stek[Uk]:=v;
{ }
Visit[v]:=false;
while Uk<>0 do { }
begin
{ }
v:=Stek[Uk];
{ t, v v->t}
t:=0; f:=false;
repeat
{ t v}
if (C[v,t]=1) and (Visit[t]) then
f:= true
else t:=t + 1;
until f or (t>n);{ }
if f then
begin
{ }
write(t:3);
Uk:=Uk+1;
Stek[Uk]:=t;
{ }
Visit[t]:=false;
end
else Uk:=Uk-1; { }
{ }
end;
end; {procedure}
begin
writeln( );
writeln( ); readln(v);
DFS(v); { v}
end.
:
1: , . 1, . 8. .
2: . .
3: , .
:
1.
, , . .
. . ( , )
2 , .
v w . ( ) v . .
|
|
4 . .
4 . , .
, DFS, (, , ). ( ). .
, , ( , ). , .
, , . , .
9, , .
2
1. . .
, , , .
(Visual Basic, Delphi).
2. . v w. . . (Visual Basic, Delphi).
.
FS
: ( ).
. :
() , ;
() ;
() ;
;
;
;
.