G - V ( ) E: G=(V, E). , , - . , . , , - .
, , , ' , , .
, ' . . .
, . .
1.
. . :
, , , .
, , .
( ), , .
Var Visited: array[1..N] of Boolean;
. false ( ). .
, v - :
Procedure DepthSearch(v: Integer);
Var j: Integer;
Begin Visited[v]:= True;
Write(' ', v, '.');
for j:= 1 to Graph[v].Count do
if not Visited[Graph[v].List[j].Node] then
DepthSearch(Graph[v].List[j].Node);
end;
, , , ( , ).
Procedure DepthSearch2(v: Integer);
Var
Way: array[1..N] of
record { }
Node, { }
Number: Integer; { }
{ }
end;
Count: Integer; { () }
{}
Current, j: Integer;
Found: Boolean;
begin
Count:=1; Way[Count].Node:=v; Way[Count].Number:=0;
Visited[v]:= True;
Write(' ', v, '.');
repeat
Current:= Way[Count].Node;
Found:= False;
for j:=Way[Count].Number+1 to Graph[Current].Count do
begin
if not Visited[Graph[Current].List[j]] then
begin
Inc(Count);
Way[Count].Node:= Graph[Current].List[j];
Way[Count].Number:= 0;
Visited[Graph[Current].List[j]]:= True;
|
|
Write(' ', Graph[Current].List[j],
'.');
Found:= True;
Break;
end;
end;
if not Found then Dec(Count);
until Count = 0;
end;
2.
, . . i- , i , .
, . , , .
Procedure WidthSearch(v: Integer);
Procedure WidthSearch(v: Integer);
Var Delayed: array[1..N] of Integer; {}
Count, { }
Head: Integer; { }
Current, j: Integer;
begin
Count:= 1; Head:= 0; Delayed[Count]:= v;
Visited[v]:= True;
Write(' ', v, '.');
repeat
Inc(Head); Current:= Delayed[Head];
for j:= 1 to Graph[Current].Count do
if not Visited[Graph[Current].List[j]] then
begin
Inc(Count);
Delayed[Count]:= Graph[Current].List[j];
Visited[Graph[Current].List[j]]:= True;
Write(' ', Graph[Current].List[j],
'.');
end;
until Count = Head;
end;