: : ( );
, .
4 .
, .
;
.
. . .
G V E. G=(V, E). , . . , . , , - .
. , . . , , .
, , , , , .
x y, (x, y), . (x, y), x y, .
, .
.
. , , , . , .
, , , .
, .
, 1 N, 1 M. .
:
- x y;
- x;
- (x, y);
- x;
- (x, y);
- , x;
- , s.
|
|
N*N:
Type TAdjacencyMatrix = array [1..N, 1..N] of Integer;Var Graph: TAdjacencyMatrix;
O(N2).
x y | T(1) |
x | T(N) |
(x, y) | T(1) |
x | T(1) |
(x, y) | T(N2) |
, x | |
, s |
, .
N*M:
Type TIncidenceMatrix = array [1..N, 1..M] of Integer;Var Graph: TIncidenceMatrix;O(N*M).
x y | T(M*N) |
x | T(M*N) |
(x, y) | T(M*N) |
x | |
(x, y) | T(M) |
, x | T(M) |
, s | T(N) |
, x.
N, :
Type TAdjacencyList = array [1..N] of record Count: Integer; { } List: array[1..N] of record {} Node, { } Weight: Integer; { } end;; end;Var Graph: TAdjacencyList;O(N2).
x y | T(N) |
x | T(N) |
(x, y) | T(N) |
x | |
(x, y) | T(M) |
x | |
s |
, N .
x
N, :
Type TBranchList = array [1..M] of record Node1, Node2, { , } Weight: Integer; { } end;Var Graph: TBranchList;O(M).
x y | T(M) |
x | T(M) |
(x, y) | T(M) |
x | |
(x, y) | T(M) |
x | T(M) |
s | T(1) |
, , , , , .
|
|
. , . . .
, . .
. . :
1. , , , .
2. , , .
3. ( ), , .
:
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;
- , . . i- , i , .
, . , , .
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;
|
|