Nelineární datové struktury
Graf
 Tisk

Graf


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.


Maticový popis grafu


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ů.


Implementace grafu spojovými seznamy

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.