posledná zmena: 10.4.2002

9.4.2002

čo sme sa doteraz naučili

dynamické štruktúry údajov: zoznamy a stromy

čo sa budeme dnes učiť

rôzne reprezentácie údajovej štruktúry graf

Grafy

graf sa skladá

z množiny vrcholov V={V₁,V₂,...}
z množiny hrán H; hrana je dvojica (v,w), kde v,w ÎV

ak je dvojica neusporiadaná => neorientovaný graf
ak je dvojica usporiadaná => orientovaný graf

znázornenie grafu:

vrcholy sú kolieska
hrany sú spojovníky, ak je graf orientovaný, tak šípky

aplikácie:

mestá spojené cestami (neorientovaný graf)
susediace štáty (oblasti)
skupina ľudí, ktorí sa navzájom poznajú

ak existuje hrana (v,w) - tak v a w sú susediace vrcholy
cesta = postupnosť vrcholov z V, kde (c_i,c_i+1) ÎH
cyklus = cesta, pre ktorú (c_n,c₁) ÎH
súvislý graf (spojitý) - ak pre každé dva vrcholy v,w ÎV existuje cesta z v do w

ne/súvislý bez cyklov (acyklický)
ne/súvislý s cyklom

neorientovaný strom (voľný strom) = súvislý neorientovaný graf bez cyklov
normálny strom = acyklický orientovaný graf, do každého vrcholu vedie 1 hrana

okrem koreňa - z neho existuje cesta do všetkých ostatných vrcholov

orientovaný graf je

silne súvislý - ak z každého existuje cesta do každého
slabo súvislý - ak by bez orientácie bol súvislý

hrana (v,v) => slučka (bude to veľmi zriedkavé - upozorníme na to)
informácie v grafe:

v každom vrchole (podobne ako v strome)
každá hrana má nejakú hodnotu (váha) => ohodnotený graf

napr. vzdialenosť miest, cena cestovného lístka, ...

komponent - súvislý podgraf - disjunktný so zvyškom grafu

Reprezentácie grafu

a. Pole množín susedov

Graf je množina vrcholov V, pre každý vrchol v Î V existuje množina A_v - množina susedov, kde A_v je podmnožinou V:

pole množín susedov:

type
  TVrcholy = 0..max-1
  TGraf = class
  private
    g:array[TVrcholy] of set of TVrcholy;
  public
    constructor Create;
    procedure pridajHranu(a,b:TVrcholy);
    procedure zrusHranu(a,b:TVrcholy);
    function jeHrana(a,b:TVrcholy):boolean;
  end;

constructor TGraf.Create;
var
  i:TVrcholy;
begin
  for i:=low(TVrcholy) to high(TVrcholy) do g[i]:=[];
end;

procedure TGraf.pridajHranu(a,b:TVrcholy);
begin
  g[a]:= g[a] + [b];
  g[b]:= g[b] + [a];        // pre neorientovaný graf
end;

procedure TGraf.zrusHranu(a,b:TVrcholy);
begin
  g[a]:= g[a] - [b];
  g[b]:= g[b] - [a];        // pre neorientovaný graf
end;

function TGraf.jeHrana(a,b:TVrcholy):boolean;
begin
  Result:=b in g[a];
end;

ak je v každom vrchole nejaká informácia:

type
  TGraf = class
    g:array[TVrcholy] of
        record                 // class
          sus:set of TVrcholy;
          meno:string;
          x,y:integer;
        end;
    constructor Create;
    procedure pridajHranu(a,b:TVrcholy);
    procedure zrusHranu(a,b:TVrcholy);
    function jeHrana(a,b:TVrcholy):boolean;
  end;

Pozn.

pre neorientovaný graf musí platiť, že ak w Î g[v], potom aj v Î g[w]

problémy:

len do 256 vrcholov
nedajú sa takto reprezentovať ohodnotené grafy (t.j. nejaká informácia na hranách)

b. Tabuľka susedností

pre každú dvojicu vrcholov v a w je hodnota v tabuľke true, ak (v,w) Î H
pre grafy s ohodnotenými hranami = 0 znamená neexistujúcu hranu, <> 0 znamená hranu s danou hodnotou

tabuľka susedností znamená dvojrozmernú maticu hrán:

type
  TVrcholy = 0..max-1
  TVaha = integer;
  TGraf = class
  private
    g:array[TVrcholy,TVrcholy] of TVaha;       // boolean - pre neohodnotený graf
  public
    constructor Create;
    procedure pridajHranu(a,b:TVrcholy; v:TVaha);
    procedure zrusHranu(a,b:TVrcholy);
    function jeHrana(a,b:TVrcholy):boolean;
  end;

constructor TGraf.Create;
var
  i,j:TVrcholy;
begin
  for i:=low(TVrcholy) to high(TVrcholy) do
    for j:=low(TVrcholy) to high(TVrcholy) do
      g[i,j]:=0;
  // alebo fillchar(g,sizeof(g),0);
end;

procedure TGraf.pridajHranu(a,b:TVrcholy; v:TVaha);
begin
  g[a,b]:=v;
  g[b,a]:=v;        // pre neorientovaný graf
end;

procedure TGraf.zrusHranu(a,b:TVrcholy);
begin
  g[a,b]:=0;
  g[b,a]:=0;        // pre neorientovaný graf
end;

function TGraf.jeHrana(a,b:TVrcholy):boolean;
begin
  Result:=g[a,b]<>0;
end;

c. Pole spájaných zoznamov susedov

Jednorozmerné pole jednosmerných spájaných zoznamov:

type
  TVrcholy = 0..max-1;
  THrana = class
    cislo:TVrcholy;
    next:THrana;
    vaha:integer;        // pre ohodnotené hrany
    constructor Create(c:TVrcholy; v:integer; n:THrana);
  end;

  TGraf = class
  private
    g:array[TVrcholy] of THrana;
  public
    constructor Create;
    procedure pridajHranu(a,b:TVrcholy; v:integer);
    procedure zrusHranu(a,b:TVrcholy);
    function jeHrana(a,b:TVrcholy):boolean;
  end;

constructor THrana.Create(c:TVrcholy; v:integer; n:THrana);
begin
  cislo:=c; vaha:=v; next:=n;
end;

constructor TGraf.Create;
var
  i:TVrcholy;
begin
  for i:=low(TVrcholy) to high(TVrcholy) do g[i]:=nil;
end;

procedure TGraf.pridajHranu(a,b:TVrcholy; v:integer);
begin
  zrusHranu(a,b);
  g[a]:=THrana.Create(b,v,g[a]);
  zrusHranu(b,a);                   // pre neorientovaný graf
  g[b]:=THrana.Create(a,v,g[b]);
end;

procedure TGraf.zrusHranu(a,b:TVrcholy);
var
  s,t:THrana;
begin
  if g[a]<>nil then begin
    s:=g[a];
    if s.cislo=b then begin
      g[a]:=s.next; s.Free;
    end
    else begin
      while (s.next<>nil) and (s.next.cislo<>b) do s:=s.next;
      if s.next<>nil then begin
        t:=s.next; s.next:=t.next; t.Free;
      end;
    end;
  end;
  if g[b]<>nil then begin
    s:=g[b];
    if s.cislo=a then begin
      g[b]:=s.next; s.Free;
    end
    else begin
      while (s.next<>nil) and (s.next.cislo<>a) do s:=s.next;
      if s.next<>nil then begin
        t:=s.next; s.next:=t.next; t.Free;
      end;
    end;
  end;
end;

function TGraf.jeHrana(a,b:TVrcholy):boolean;
var
  s:THrana;
begin
  s:=g[a];
  while (s<>nil) and (s.cislo<>b) do s:=s.next;
  Result:=s<>nil;
end;

Pozn.

ak potrebujeme mať vo vrcholoch ďalšie informácie, tak v triede TGraf vytvoríme nové pole alebo pole g bude pole vrcholov (record alebo class), pričom každý vrchol okrem zoznamu hrán obsahuje aj nejakú svoju informáciu, napr. meno, x,y - poloha pri vykreslení do plochy a pod.

d. Zoznam zoznamov vrcholov

Graf ako jednosmerný spájaný zoznam všetkých vrcholov grafu, pričom v každom vrchole je začiatok spájaného zoznamu hrán, ktoré vychádzajú z tohto vrcholu - každá hrana obsahuje smerník na vrchol (do prvého zoznamu), s ktorým je daný vrchol spojený touto hranou.

zoznam zoznamov:

type
  THrana = class            // každý záznam reprezentuje jednu hranu
    p:TVrchol;              // niektorý vrchol grafu
    // TVaha:integer;
    next:THrana;
  end;

  TVrchol = class
    sus:THrana;            // zoznam susedov = zoznam hrán z daného vrcholu
    // meno,x,y,...;       // informácia o vrchole
    next:TVrchol;
  end;

  TGraf = TVrchol;          // prvý vrchol v spájanom zozname všetkých vrcholov

e. Dynamické pole dynamických polí

Graf je pole vrcholov, pričom každý vrchol obsahuje pole hrán - zoznam svojich susediacich vrcholov.

dynamické pole dynamických polí:

type
  TVaha = integer;
  THrana = class
    cislo:integer;      // poradové číslo vrcholu, do ktorého vedie hrana
    vaha:TVaha;         // pre ohodnotené hrany
    constructor Create(c:integer; v:TVaha);
  end;

  TVrchol = class
  private
    meno:string;
    x,y:integer;
    sus:array of THrana;
    function indexHrany(c:integer):integer;
  public
    constructor Create(m:string; xx,yy:integer);
    procedure pridajHranu(c:integer; v:TVaha);
    procedure zrusHranu(c:integer);
    procedure zmenVahuHrany(c:integer; v:TVaha); overload;
    procedure zmenVahuHrany(s:THrana; v:TVaha); overload;
    function jeHrana(c:integer):boolean;
  end;

  TGraf = class
  private
    g:array of TVrchol;
  public
    constructor Create;
    procedure pridajVrchol(m:string; xx,yy:integer);
    procedure zrusVrchol(c:integer);
    procedure pridajHranu(c1,c2:integer; v:TVaha); overload;
    procedure pridajHranu(v1,v2:TVrchol; v:TVaha); overload;
    procedure zrusHranu(c1,c2:integer);
    procedure zmenVahuHrany(c1,c2:integer; v:TVaha);
    function jeHrana(c1,c2:integer):boolean;
  end;

{ THrana }

constructor THrana.Create(c:integer; v:TVaha);
begin
  cislo:=c; vaha:=v;
end;

{ TVrchol }

constructor TVrchol.Create(m:string; xx,yy:integer);
begin
  meno:=m;
  x:=xx; y:=yy;
  sus:=nil;
end;

function TVrchol.indexHrany(c:integer):integer;
begin
  Result:=high(sus);
  while (Result>=0) and (sus[Result].cislo<>c) do dec(Result);
end;

function TVrchol.jeHrana(c:integer):boolean;
begin
  Result:=indexHrany(c)>=0;
end;

procedure TVrchol.pridajHranu(c:integer; v:TVaha);
begin
  if not jeHrana(c) then begin
    SetLength(sus,Length(sus)+1);
    sus[high(sus)]:=THrana.Create(c,v);
  end;
end;

procedure TVrchol.zrusHranu(c:integer);
var
  i:integer;
begin
  i:=indexHrany(c);
  if i>=0 then begin
    sus[i].Free; sus[i]:=sus[high(sus)];
    SetLength(sus,high(sus));
  end;
end;

procedure TVrchol.zmenVahuHrany(c:integer; v:TVaha);
var
  i:integer;
begin
  i:=indexHrany(c);
  if i>=0 then sus[i].vaha:=v;
end;

procedure TVrchol.zmenVahuHrany(s:THrana; v:TVaha);
var
  i:integer;
begin
  i:=0;
  while (i<=high(sus)) and (sus[i]<>s) do inc(i);
  if i<=high(sus) then sus[i].vaha:=v;
end;

{ TGraf }

constructor TGraf.Create;
begin
  g:=nil;
end;

procedure TGraf.pridajVrchol(m:string; xx,yy:integer);
begin
  SetLength(g,Length(g)+1);
  g[high(g)]:=TVrchol.Create(m,xx,yy);
end;

procedure TGraf.zrusVrchol(c:integer);
var
  i,j:integer;
begin
  if c<=high(g) then begin
    for i:=0 to high(g) do zrusHranu(i,c);
    g[c].Free;
    for i:=c to high(g)-1 do g[i]:=g[i+1];
    SetLength(g,high(g));
    for i:=0 to high(g) do
      for j:=0 to high(g[i].sus) do
        if g[i].sus[j].cislo>c then dec(g[i].sus[j].cislo);
  end;
end;

procedure TGraf.pridajHranu(c1,c2:integer; v:TVaha);
begin
  if (c1<=high(g)) and (c2<=high(g)) then
    if not jeHrana(c1,c2) then begin
      g[c1].pridajHranu(c2,v);
      g[c2].pridajHranu(c1,v);     //pre neorientovany graf
    end
    else
      zmenVahuHrany(c1,c2,v);
end;

procedure TGraf.pridajHranu(v1,v2:TVrchol; v:TVaha);
var
  i,j:integer;
begin
  i:=0; while (i<=high(g)) and (g[i]<>v1) do inc(i);
  j:=0; while (j<=high(g)) and (g[j]<>v2) do inc(j);
  if (i<=high(g)) and (j<=high(g)) then
    pridajHranu(i,j,v);
end;

procedure TGraf.zrusHranu(c1,c2:integer);
begin
  if (c1<=high(g)) and (c2<=high(g)) then begin
    g[c1].zrusHranu(c2);
    g[c2].zrusHranu(c1);     // pre neorientovane grafy
  end;
end;

procedure TGraf.zmenVahuHrany(c1,c2:integer; v:TVaha);
begin
  if (c1<=high(g)) and (c2<=high(g)) then
    g[c1].zmenVahuHrany(c2,v);
end;

function TGraf.jeHrana(c1,c2:integer):boolean;
begin
  if (c1<=high(g)) and (c2<=high(g)) then
    Result:=g[c1].jeHrana(c2)
  else Result:=false;
end;

vykreslenie grafu do grafickej plochy:

type
  ...

  TVrchol = class
    ...
    procedure Kresli(c:TCanvas);
  end;

  TGraf = class
    ...
    procedure Kresli(c:TCanvas);
  end;

...

procedure TVrchol.Kresli(c:TCanvas);
begin
  c.Ellipse(x-8,y-8,x+8,y+8);
  c.TextOut(x-6,y-6,meno);
end;

procedure TGraf.Kresli(c:TCanvas);
var
  i,j,xx,yy:integer;
begin
  with c do begin
    Brush.Style:=bsClear;
    for i:=0 to high(g) do
      with g[i] do begin
        Pen.Color:=clBlue;
        Kresli(c);           // vykreslí vrchol ako kružnicu
        Pen.Color:=clGreen;
        for j:=0 to high(sus) do begin
          with g[sus[j].cislo] do begin xx:=x; yy:=y; end;
          MoveTo(x,y);
          LineTo(xx,yy);
          TextOut((x+xx) div 2,(y+yy) div 2,IntToStr(sus[j].vaha));
        end;
      end;
  end;
end;

Takýto graf môžeme otestovať napríklad takto:

jednoduchý test:

var
  g:TGraf;

procedure TForm1.FormCreate(Sender: TObject);
begin
  randomize;
  g:=TGraf.Create;
  g.pridajVrchol('prvy',random(600),random(600));
  g.pridajVrchol('druhy',random(600),random(600));
  g.pridajVrchol('treti',random(600),random(600));
  g.pridajHranu(0,1,10);
  g.pridajHranu(0,2,20);
  g.pridajHranu(1,2,30);
  g.Kresli(Image1.Canvas);
end;

Nasledujúci príklad ilustruje pridávanie vrcholov a hrán do grafu:

spracovanie kliknutia do grafickej plochy:

var
  g:TGraf;
  pocet:integer = 0;

procedure TForm1.FormCreate(Sender: TObject);
begin
  DoubleBuffered:=true;
  randomize;
  g:=TGraf.Create;
end;

procedure TForm1.Image1MouseDown(...);
var
  i:integer;
begin
  g.pridajVrchol(IntToStr(pocet+1),X,Y);
  for i:=0 to pocet-1 do
    if random(2)=0 then
      g.PridajHranu(i,pocet,random(100));
  g.Kresli(Image1.Canvas);
  inc(pocet);
end;

Pozn.

tento príklad negeneruje úplný graf, ale s pravdepodobnosťou 0.5 spojí nový vrchol s už existujúcimi
v tomto príklade si všimnite, že potrebujeme pomocnú premennú (pocet) na zapamätanie si počtu vrcholov v grafe - momentálna definícia grafu (keď g je privátna stavová premenná) nám neposkytuje žiadnu takú informáciu

NDÚ:

doplňte do definície grafu metódy, resp. vlastnosti (property) tak, aby sa pohodlnejšie pracovalo s existujúcimi vrcholmi a hranami
vygenerujte graf s N vrcholmi, ktoré ležia vo vrcholoch pravidelného N-uholníka, v ktorom

každé dva vrcholy sú spojené hranou
každý i-ty vrchol je spojený s (i+2)-tym vrcholom - (N-1) s prvým a N-tý s druhým
je práve K náhodne vygenerovaných hrán

daný graf vykreslite tak, že v každom vrchole vypíšete číslo - počet hrán, ktorá z neho vychádzajú (tzv. árnosť vrcholu)
pre daný graf zistite počet izolovaných vrcholov