Graf je dynamická nelineární datová struktura, která dovoluje vyjadřovat vazby mezi prvky. Prvky se nazývají vrcholy nebo uzly grafu (nodes, vertex - vertices), vazby mezi objekty jsou hrany grafu (edges).
Příklady:
Každé hraně v grafu přísluší dvojice vrcholů. Hrana tyto vrcholy spojuje. Pokud je dvojice vrcholů, příslušejících jednotlivým hranám, orientovaná (můžeme si představit, že silnice mezi městy jsou jednosměrné), jde o graf orientovaný, jinak o graf neorientovaný.
S hranami i vrcholy mohou být spojeny další informace (např. u měst počet obyvatel, u hran vzdálenost měst). Pak hovoříme o grafu hranově nebo vrcholově ohodnoceném.
Graf můžeme vyjádřit buď pomocí dvourozměrné matice, nebo dynamickými seznamy vrcholů a hran.
Známe-li maximální počet vrcholů v grafu (nejčastější případ), dají se někdy operace nad grafem převést na maticové operace. Graf je reprezentován tzv. incidenční maticí (dvojrozměrným polem) . Ta vyjadřuje incidenci (sousedních) vrcholů. Snadno se realizují operace přidání hrany, odebrání hrany, test existence hrany. Obtížněji se pracuje s vrcholy. Typickým příkladem je např. návrh (analýza) elektrických sítí.
Při reprezentaci grafu hranově-vrcholovou incidenční maticí jsou vrcholy identifikovány čísly řádků a sloupců, hrany pozicemi matice.
Sledujeme-li řádek v matici zleva doprava, vyjadřují prvky matice booleovskými hodnotami, do kterých uzlů se z daného uzlu orientovanou hranou lze dostat. Sledujeme-li v matici sloupec shora dolů, zjistíme, ze kterých uzlů se lze dostat do uzlu sledovaného.
Pro potřeby implementace grafu dvojrozměrným pole zavedeme deklarace typů:
Type
TVrchol = 1 .. MaxV; { Maximální počet vrcholů }
TGraf = array[TVrchol,TVrchol] of Boolean;
Přidání a ubrání v orientovaném grafu realizují operace:
procedure PRIDEJHRANU(var G : TGraf; V1,V2 : TVrchol);
{ Přidá hranu z V1 do V2 }
begin
If not G[V1,V2] then G[V1,V2] := true
else Write(' Tato hrana již existuje ')
end;
procedure UBERHRANU(var G : TGraf; V1,V2 : TVrchol);
{ Zruší hranu z V1 do V2 }
begin
If G[V1,V2] then G[V1,V2] := false
else Write(' Tato hrana neexistuje ')
end;
Důležitý je pojem tzv. Tranzitivní uzávěr grafu . Je to incidenční matice, která popisuje vzájemnou dosažitelnost všech vrcholů bez ohledu na to, jak složitou cestou se toho dosáhne.
Program Graff; {Tranzitivní uzávěr grafu implementovaného maticí }
Const
MaxV = 6;
Type
TVrchol = 1 .. MaxV; { Maximalni pocet vrcholu; }
TGraf = array[TVrchol,TVrchol] of Boolean;
Var
Graf: TGraf;
Procedure TRANZIT(var PuvInc, TranzUzav : TGraf);
Var
I,J,K : 1 .. MaxV;
Begin
TranzUzav := PuvInc;
for I := 1 to MaxV do
for J := 1 to MaxV do
if TranzUzav[J,I] then { Existuje-li cesta z J do I a }
for K := 1 to MaxV do
if TranzUzav[I,K] { existuje-li cesta z I do K, }
then TranzUzav[J,K] := true { pak existuje i cesta z J do K }
end;
Procedure Cteni(var MAT : TGraf);
Var
I,J : 1 .. MaxV;
a:char;
Begin
for I := 1 to MaxV do
for J := 1 to MaxV do begin
write('Zapis hodnotu matice pro [',I,',',J,']');
readln(a);
if a = '0' then MAT[I,J] := false else MAT[I,J] := true
end;
end;
Procedure Tisk(var MAT : TGraf; s:string);
Var
I,J : 1 .. MaxV;
Begin
Writeln;
Writeln(s);
for I := 1 to MaxV do begin
for J := 1 to MaxV do
if MAT[I,J] = false then write(' 0') else write(' 1');
writeln;
end;
end;
begin
Cteni(Graf);
Tisk(Graf,'Puvodni graf');
Tranzit(Graf,Graf);
Tisk(Graf,'Tranzitivni uzaver');
end.
V případech, kdy se při práci s grafem mění počet uzlů, není implementace grafu maticí vhodná. Rovněž není vhodná tehdy, když incidenční matice je řídká, tj. graf obsahuje hodně vrcholů, které jsou spojeny řídce hranami. V takovém případě je vhodná implementace pomocí spojových seznamů.
Pro každý vrchol bude existovat jeden seznam a ten bude obsahovat tolik prvků, kolik z něj vychází nebo do něj vstupuje hran. U orientovaného grafu bude celkový počet prvků v seznamech rovný počtu hran, u neorientovaného grafu bude každá hrana v seznamech dvakrát.
V takové reprezentaci se dobře přidávají i ubírají hrany, dobře se přidávají vrcholy, více práce je s rušením vrcholu, protože se musí vyjmout ze všech seznamů prvky, odpovídající hranám vycházejícím nebo vcházejícím do rušeného vrcholu.
Př. Program pro tranzitivní uzávěr grafu implementovaného zřetězeným seznamem.
Program Grafs; {Tranzitivní uzávěr grafu implementovaného seznamem hran }
Const
MaxV = '6';
Type
TVrchol = '1'..MaxV;
UHrana = ^THrana;
THrana = record
odkud: TVrchol;
kam: TVrchol;
dalsi: UHrana;
end;
Tgraf = UHrana;
Var
Graf, Graft: Tgraf;
Procedure Pridej(p:UHrana; var O,K:TVrchol);
Var
pom: UHrana;
Begin { Přidává na konec neprázdného seznamu hran }
new(pom);
pom^.odkud := O;
pom^.kam := K;
pom^.další := nil;
while p^.dalsi <> nil do p := p^.dalsi;
p^.další := pom;
end;
Function Exist(p:UHrana; O,K:TVrchol):Boolean;
Begin { Zjistuje, zda z vrcholu O vede hrana do K }
while (p^.dalsi <> nil) and ((p^.odkud <> O) or (p^.kam <> K)) do p := p^.dalsi;
if (p^.odkud <> O) or (p^.kam <> K) then Exist := false
else Exist := true;
end;
Procedure Kopir(var G:UHrana; p:Uhrana);
Var
pom: UHrana;
Begin { Kopíruje seznam hran na druhy }
new(pom);
G := pom;
pom^ := p^;
pom^.dalsi := nil;
while p^.dalsi <> nil do begin
p := p^.dalsi;
new(pom^.dalsi);
pom := pom^.dalsi;
pom^ := p^;
pom^.další := nil;
end;
end;
Procedure Cteni(var Gr : TGraf);
Var
konec:char;
pom,p: UHrana;
Begin
Gr := nil;
writeln;
repeat
new(pom);
repeat { Cte hranu a pridava ji na konec seznamu }
write('zadej odkud = '); readln(pom^.odkud);
until (pom^.odkud >= '1') and (pom^.odkud <= MaxV);
repeat
write('zadej kam = '); readln(pom^.kam);
until (pom^.kam >= '1') and (pom^.kam <= MaxV);
pom^.dalsi := nil;
if Gr = nil then gr := pom else begin
p := Gr;
while p^.dalsi <> nil do p := p^.dalsi;
p^.dalsi := pom;
end;
write('Dalsi = a/n'); readln(konec);
until konec = 'n';
end;
Procedure Tisk(p : TGraf; s:string);
Begin
Writeln;Writeln(s);
while p <> nil do begin
write(' (',p^.odkud,',',p^.kam,') ');
p := p^.dalsi;
end;
end;
Procedure TRANZIT(var PuvInc, TranzUzav : TGraf);
Var
I,J,K : TVrchol;
Begin {Tranzitivní uzávěr }
Kopir(TranzUzav,PuvInc);
for I := '1' to MaxV do
for J := '1' to MaxV do
if Exist(TranzUzav,J,I) then { Existuje-li cesta z J do I a }
for K := '1' to MaxV do
if Exist(TranzUzav,I,K) { existuje-li cesta z I do K, }
then Pridej(TranzUzav,J,K);{ pak existuje i cesta z J do K }
end;
begin
Cteni(Graf);
Tisk(Graf,'Puvodni graf');
Tranzit(Graf,Graft);
Tisk(Graft,'Tranzitivni uzaver');
end.