1
Ch ng4
ph c t p c acácgi ithu t th
2
N idung
1. Cácgi ithu t th c n b n
2. th có tr ng s
3. th có h ng
3
1.Cácgi ithu t th c nb n
Cónhi ubàitoán c nhngh atheo it ngvàcác
k
tn igi acác it ng y.
M t th là m t it ngtoánh cmàmôt nh ngbài
toánnh
v y.
Các
ngd ngtrongcácl nhv c:
Giaothông
Vi
nthông
i nl c
M
ngmáytính
C
s d li u
Trìnhbiênd
ch
Cách
i uhành
Lý thuy

l
pl i.
6
Thu tng (tt
M t chutrình cycle àm tl i i nngo itr nh u
tiênvà
nhcu icùngtrùngnhau tl i it m t nh
quay v
chínhnó).
M
t th khôngcóchutrình cg ilàcây(tree). M t
nhómcáccâykhôngliênthông
cg ilàr ng ( forest ).
Câybaotrùm c am t th là m t th conmàch at tc
các nhtrongcâynh ngm ts c nh ch m nm i nh.
G
is nhtrongm t th là V, s c nhlàE, s c nhc a
th có th có t 0 nV(V-1)/2.(Ch ngminhtruych ng).
th có t tc m ic nhhi ndi ngi am ic p nh c
g ilà th y (complete graphs).
7
Thu tng (tt
Các th v is c nht ng i ít cg ilà th th a;
các
th v ich m ts ítc nhm t i cg ilà th dày.
Các
th mô t cho ngi là nh ng th vô h ng
undirected graphs .Trongcác th có tr ngs weighted
graphs
, nh nggiá tr s (tr ngs ) cg nvàom ic nh

C 10 1000 0 00 0 0 0 0
D 00 0111 0 00 0 0 0 0
E 00 0111 1 00 0 0 0 0
F 10 0111 0 00 0 00 0
G1 0 0010 100 00 0 0
H 00 0000 011 00 0 0
I 00 0 000 011 00 0 0
J0 0 000 0 0 00 1 1 1 1
K 00 0000 0 00 1 1 0 0
L0 00000 0 00 1 01 1
M0 0 0000 0 00 1 01 1
M
tmatr nV
hàngV c
tch a
cácgiá tr
Boolean
mà a[x,y] là true if
n
ut nt im t
c
nht nh x n
nh y và false n u
ng
cl i.
Hình4.1b: Ma tr
nk
c nc a th hình
4.1a
10

Trongcáchbi udi nnày, m i nhmàn it im t
nh ck tthànhm tdanhsáchk c n
(adjacency list )cho nh ó.
program adjlist(input, output);
const maxV= 100;
type link=↑node
node=record v: integer; next:link end;
var j,x, y,V,E: integer;
t,x:link;
adj: array[1 maxV] of link;
13
begin
readln(V,E);
new(z); z↑.next:=z;
for j:=1to V do adj[j]:=z;
for j: 1 to E do
begin
readln(v1, v2);
x:= index(v1); y:=index(v2);
new(t); t↑.v:=x; t↑.next:=adj[y];
adj[y]:=t; /*insert xtothefirst element of
y’sadjacencylist*/
new(t); t↑.v= y; t↑.next:=adj[x];
adj[x]:=t; /*insert ytothefirstelementof
x’sadjacencylist */
end;
end.
14
a bc d e f g h i j k l m
f

andadd any neighbor vertexthat has not been processed
tothestack.
if a vertex hasalreadyappearedinthestack,thereis no
needto push
ittothestack,butitismoved tothetopof thestack.
end;
begin
Initializestatus;
for eachvertex,say n, inthegraph do
if thestatusof nis “notyetvisited” then visit(n)
end;
17
T mki mtheochi usâutr c – bi udi n
danhsáchk
c n
procedure
var , k:integer;
val: array[1 maxV] of integer;
procedure visit(k:integer);
var t:link;
begin
id:= id+ 1; val[k]:= id;/*change thestatus of k
to “visited” */
t:= adj[k]; / * findtheneighborsofthevertexk */
while t<> z do
begin
if val[t ↑.v]= 0 then visit(t↑.v);
t:= t↑.next
end
end;

A
F
E
G
A
F
E
G
A
F
E
G
A
F
E
G
A
F
E
G
A
F
G
E
A
G
E
A
G
E

th bi udi nb ngcácdanhsáchk c n òih ith i
giant
l V E.
Ch ngminh:Chúngtaph igántr chom iph n
t
c am ng val (do ó t l v iO(V)),vàxétm i
núttrongcácdanhsáchk
tc nbi udi n th (do
ó t l v iO(E)).
22
ttheochi usâutr c bi udi nb ngma
tr
nk c n
Cùngm tph ngphápcóth c ápd ngcho
th cbi udi nb ngmatr nk c nb ng
cáchdùngth
t c visit sau ây:
procedure
(
var
begin
id+ 1; val[k]:= id;
for t:=1to V do
if a[k,t] then
if val[t]= 0 then visit(t)
end;
23
ph ct pc aduy ttheochi usâutr c –
bi
udi nmatr n

0; stackinit;
for k:= 1 to V do val[k]:=0;/* initialize the
status of allvertices*/
for k:= 1 to V do
if val[k]= 0 then visit(k)
end;
V
igi ithu tkhông quy,tac ndùngm tstack cg i
là
readystack.
Ghichú
:
val[k] = 0 n
u nh k l ch a cvi ngth m ,
val[k] = -1 n
u nh k ang trongreadystack
val[k] là m
ttr d ngn u nh k cvi ngth m.