31.Prednaska

Z Pascal
Prejsť na: navigácia, hľadanie
31. Prednáška

úlohy | cvičenie


Reprezentácie grafov

Graf je dátová štruktúra, ktorá sa skladá

  • z množiny vrcholov V = {V1, V2, ...}
  • z množiny hrán H, pričom každá hrana je dvojica (v, w), kde v, w in V
    • ak je to neusporiadaná dvojica, hovoríme tomu neorientovaný graf
    • ak je to usporiadaná dvojica, hovoríme tomu orientovaný graf

Graf budeme znázorňovať takto:

  • vrcholy sú kolieska
  • hrany sú spojovníky medzi vrcholmi, pričom, ak je graf orientovaný, tak spojovníkmi sú šípky

Graf najčastejšie používame, keď potrebujeme vyjadriť takéto situácie:

  • mestá spojené cestami (najčastejšie je to neorientovaný graf: mestá sú vrcholy, hrany označujú cesty medzi mestami)
  • križovaky a ulice v meste (križovatky sú vrcholy, hrany sú ulice medzi križovatkami)
  • susediace štáty alebo nejaké oblasti (štáty sú vrcholy, hrany označujú, že nejaké štáty susedia)
  • mestská verejná doprava (zastávky sú vrcholy, hrany označujú, že existuje linka, ktorá má tieto dve susediace zastávky)
  • skupina ľudí, ktorí sa navzájom poznajú (ľudia sú vrcholy, hrany označujú, že nejaké konkrétne dve osoby sa poznajú)

Dôležité pojmy:

  • ak existuje hrana (v, w) - tak v a w sú susediace vrcholy
  • cesta je postupnosť vrcholov z množiny V, kde (ci, ci+1) in H
  • cyklus je taká cesta, pre ktorú (cn, c1) in H
  • hovoríme, že graf je súvislý (spojitý), ak pre každé dva vrcholy v, w in V, existuje cesta z v do w
  • niekedy bude pre nás dôležité, keď nejaký graf bude súvislý/nesúvislý bez cyklov (tzv. acyklický), ale aj súvislý/nesúvislý s cyklom
  • neorientovaný strom (voľný strom) je súvislý neorientovaný graf bez cyklov
  • normálny strom je acyklický orientovaný graf, do každého vrcholu vedie len 1 hrana a to okrem tzv. koreňa, t.j. špeciálneho vrcholu, z ktorého existuje cesta do všetkých ostatných vrcholov
  • orientovaný graf môže byť
    • silne súvislý, ak z každého vrcholu existuje cesta do každého
    • slabo súvislý, ak by bez orientácie hrán bol silne súvislý
  • hrane (v, v) hovoríme slučka (toto bude veľmi zriedkavé, ak sa to niekedy objaví, upozorníme na to)
  • v grafe môžeme mať uchované rôzne informácie:
    • v každom vrchole (podobne ako v strome)
    • každá hrana má nejakú hodnotu (tzv. váha), vtedy tomu hovoríme ohodnotený graf, napr. vzdialenosť dvoch miest, cena cestovného lístka, linky, ktoré spájajú dve zastávky, ...
  • pojem komponent označuje súvislý podgraf, ktorý je disjunktný so zvyškom grafu

Ďalej ukážeme najčastejšie spôsoby reprezentácie grafov. Konkrétna reprezentácia sa potom zvolí väčšinou podľa problémovej oblasti a rôznych obmedzení v zadaní.


Pole množín susedov

Graf je množina vrcholov V, pre každý vrchol v in V existuje množina Av - množina susedov, kde Av je podmnožinou V. Napr. pre graf s 10 vrcholmi to môžeme zapísať takto:

type
  TGraf = class
    G: array [1..10] of set of 1..10;
    constructor Create;
    procedure PridajHranu(A, B: Integer);
    procedure ZrusHranu(A, B: Integer);
    function JeHrana(A, B: Integer): Boolean;
  end;
 
constructor TGraf.Create;
var
  I: TVrcholy;
begin
  for I := Low(G) to High(G) do
    G[I] := [];
end;
 
procedure TGraf.PridajHranu(A, B: Integer);
begin
  G[A] := G[A] + [B];
  G[B] := G[B] + [A];        // pre neorientovaný graf
end;
 
procedure TGraf.ZrusHranu(A, B: Integer);
begin
  G[A] := G[A] - [B];
  G[B] := G[B] - [A];        // pre neorientovaný graf
end;
 
function TGraf.JeHrana(A, B: Integer): Boolean;
begin
  Result := B in G[A];
end;

Každý vrchol grafu môže byť objektom. Potom to okrem množiny susedov môžeme uchovať aj ďalšie informácie:

type
  TVrchol = class
    Sus: set of 1..10;
    Meno: string;
    X, Y: Integer;
    constructor Create(...);
  end;
 
  TGraf = class
    G: array [1..10] of TVrchol;
    constructor Create;
    procedure PridajHranu(A, B: Integer);
    procedure ZrusHranu(A, B: Integer);
    function JeHrana(A, B: Integer): Boolean;
  end;

Obmedzenia pre túto reprezentáciu:

  • môžeme použiť maximálne do 256 vrcholov
  • nedajú sa takto reprezentovať ohodnotené grafy (t.j. keď potrebujeme uchovať aj nejakú informáciu na hranách)


Poznámky:

  • pre neorientovaný graf musí platiť, že ak w in G[v], potom aj v in G[w]
  • ak namiesto intervalu 1..10 zapíšeme typ Byte, dostaneme graf maximálnych rozmerov pre túto reprezentáciu
    • niekedy sa namiesto statického poľa G používa dynamické pole


Tabuľka susedností

Táto reprezentácia využíva dvojrozmerné pole (veľkosti NxN), v ktorom pre každú dvojicu vrcholov v a w je hodnota v tabuľke True, ak (v, w) in H. Tabuľka susedností teda znamená dvojrozmernú maticu hrán:

type
  TGraf = class
  private
    G: array [1..N, 1..N] of Boolean;
  public
    constructor Create;
    procedure PridajHranu(A, B: Integer);
    procedure ZrusHranu(A, B: Integer);
    function JeHrana(A, B: Integer): Boolean;
  end;
 
constructor TGraf.Create;
var
  I, J: TVrcholy;
begin
  for I := 1 to N do
    for J := 1 to N do
      G[I, J] := False;
end;
 
procedure TGraf.PridajHranu(A, B: Integer);
begin
  G[A, B] := True;
  G[B, A] := True;        // pre neorientovaný graf
end;
 
procedure TGraf.ZrusHranu(A, B: Integer);
begin
  G[A, B] := False;
  G[B, A] := False;        // pre neorientovaný graf
end;
 
function TGraf.JeHrana(A, B: Integer): Boolean;
begin
  Result := G[A, B];
end;

Pomocou tejto reprezentácie vieme pracovať aj s ohodnotenými grafmi. Vtedy bude v tabuľke namiesto hodnôt True/False hodnota váhy. Napr. pre celočíselné váhy môže hodnota 0 znamenať neexistujúcu hranu a hodnota rôzna od 0 znamenať existujúcu hranu, ktorá má túto danú hodnotu váhy. Váhou nemusí byť len celé číslo, ale aj reálne číslo, reťazec, nejaká množina alebo aj zložitejšia štruktúra.

V každom vrchole môžeme uchovať aj nejakú informáciu a potom je výhodné, aby bol každý vrchol samostatným objektom, napr. ohodnotený graf s váhou reálne číslo:

type
  TVrchol = class
    Sus: array [1..N] of Real;
    Meno: string;
    X, Y: Integer;
    constructor Create(...);
  end;
  TGraf = class
    G: array [1..N] of TVrchol;
    constructor Create;
    procedure PridajHranu(A, B: Integer; Vaha: Real);
    procedure ZrusHranu(A, B: Integer);
    function JeHrana(A, B: Integer): Boolean;
  end;

a metódy by sa zmenili napr. takto:

constructor TGraf.Create;
var
  I, J: TVrcholy;
begin
  for I := 1 to N do
  begin
    G[I] := TVrchol.Create(...);
    for J := 1 to N do
      G[I].Sus[J] := 0;
  end;
end;
 
procedure TGraf.PridajHranu(A, B: Integer; V: Real);
begin
  G[A].Sus[B] := V;
  G[B].Sus[A] := V;        // pre neorientovaný graf
end;
 
procedure TGraf.ZrusHranu(A, B: Integer);
begin
  G[A].Sus[B] := 0;
  G[B].Sus[A] := 0;        // pre neorientovaný graf
end;
 
function TGraf.JeHrana(A, B: Integer): Boolean;
begin
  Result := G[A].Sus[B] <> 0;
end;


Pole spájaných zoznamov susedov

Grafom v tejto reprezentácii je jednorozmerné pole jednosmerných spájaných zoznamov. Každý prvok tohto poľa reprezentuje jeden vrchol grafu a pamätá sa v ňom zoznam všetkých jeho susedov. Keďže susedia sú s daným vrcholom pospájaní hranami, hovoríme tomu zoznam hrán:

type
  THrana = class
    Cislo: 1..N;
    Vaha: Real;        // pre ohodnotené hrany
    Next: THrana;
    constructor Create(C: Integer; V: Real; N: THrana);
  end;
 
  TGraf = class
  private
    G: array [1..N] of THrana;
  public
    constructor Create;
    procedure PridajHranu(A, B: Integer; Vaha: Real);
    procedure ZrusHranu(A, B: Integer);
    function JeHrana(A, B: Integer): Boolean;
  end;
 
constructor THrana.Create(C: Integer; V: Real; N: THrana);
begin
  Cislo := C;
  Vaha := V;
  Next := N;
end;
 
constructor TGraf.Create;
var
  I: TVrcholy;
begin
  for I := 1 to N do
    G[I] := nil;
end;
 
procedure TGraf.PridajHranu(A, B: Integer; V: Real);
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: Integer);
var
  Zoznam, Pom: THrana;
begin
  if G[A] <> nil then
  begin
    Zoznam := G[A];
    if Zoznam.Cislo = B then
    begin
      G[A] := Zoznam.Next;
      Zoznam.Free;
    end
    else
    begin
      while (Zoznam.Next <> nil) and (Zoznam.Next.Cislo <> B) do
        Zoznam := Zoznam.Next;
      if Zoznam.Next <> nil then
      begin
        Pom := Zoznam.Next;
        Zoznam.Next := Pom.Next;
        Pom.Free;
      end;
    end;
  end;
  if G[B] <> nil then
  begin
    Zoznam := G[B];
    if Zoznam.Cislo = A then
    begin
      G[B] := Zoznam.Next;
      Zoznam.Free;
    end
    else
    begin
      while (Zoznam.Next <> nil) and (Zoznam.Next.Cislo <> A) do
        Zoznam := Zoznam.Next;
      if Zoznam.Next <> nil then
      begin
        Pom := Zoznam.Next;
        Zoznam.Next := Pom.Next;
        Pom.Free;
      end;
    end;
  end;
end;
 
function TGraf.JeHrana(A, B: Integer): Boolean;
var
  Zoznam: THrana;
begin
  Zoznam := G[A];
  while (Zoznam <> nil) and (Zoznam.Cislo <> B) do
    Zoznam := Zoznam.Next;
  Result := Zoznam <> nil;
end;

Ak potrebujeme mať vo vrcholoch ďalšie informácie, tak najčastejšie bude pole G v triede TGraf poľom vrcholov (objektov), pričom každý vrchol okrem zoznamu hrán obsahuje aj nejakú svoju informáciu, napr. Meno, X, Y a pod. Napr.

type
  TVrchol = class
    Sus: THrana;      // zoznam susedov
    Meno: string;
    X, Y: Integer;
    constructor Create(...);
  end;


Zoznam zoznamov vrcholov

Táto reprezentácie je ešte zovšeobecnením predchádzajúcej. Tu už vrcholy netvoria jednorozmerné pole, ale sú zoradené v jednosmernom spájanom zozname. V každom vrchole je potom uložený začiatok jeho vlastného spájaného zoznamu hrán (hrán, ktoré vychádzajú z tohto vrcholu). Každá takáto hrana obsahuje smerník na vrchol (t.j. smerník do prvého zoznamu všetkých vrcholov), s ktorým je daný vrchol spojený touto hranou:

type
  THrana = class        // každý objekt 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 = class
  private
    G: TVrchol;  // prvý vrchol v spájanom zozname všetkých vrcholov
  public
    constructor Create;
    procedure PridajVrchol(...);
    procedure PridajHranu(...);
    procedure ZrusVrchol(...);
    procedure ZrusHranu(...);
    function JeHrana(...): Boolean;
    ...
  end;


Dynamické pole dynamických polí

Toto je verziou predchádzajúcej reprezentácie, v ktorej sme namiesto spájaného zoznamu použili dynamické pole. Graf je teda pole vrcholov, pričom každý vrchol obsahuje pole hrán, čo je vlastne zoznam svojich susediacich vrcholov:

type
  TVaha = Integer;
  THrana = class
    Cislo: Integer;   // poradové číslo vrcholu, do ktorého vedie hrana - index do poľa vrcholov
    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(NoveMeno: string; XX, YY: Integer);
    procedure PridajHranu(C: Integer; V: TVaha);
    procedure ZrusHranu(C: Integer);
    procedure ZmenVahuHrany(C: Integer; V: TVaha); overload;
    procedure ZmenVahuHrany(Sused: THrana; V: TVaha); overload;
    function JeHrana(C: Integer): Boolean;
  end;
 
  TGraf = class
  private
    G: array of TVrchol;
  public
    constructor Create;
    procedure PridajVrchol(NoveMeno: 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(NoveMeno: string; XX, YY: Integer);
begin
  Meno := NoveMeno;
  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(Sused: THrana; V: TVaha);
var
  I: Integer;
begin
  I := 0;
  while (I <= High(Sus)) and (Sus[I] <> Sused) do
    Inc(I);
  if I <= High(Sus) then
    Sus[I].Vaha := V;
end;
 
{ TGraf }
 
constructor TGraf.Create;
begin
  G := nil;
end;
 
procedure TGraf.PridajVrchol(NoveMeno: string; XX, YY: Integer);
begin
  SetLength(G, Length(G)+1);
  G[High(G)] := TVrchol.Create(NoveMeno, XX, YY);
end;
 
procedure TGraf.ZrusVrchol(C: Integer);
var
  I, J: Integer;
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, Length(G)-1);
  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;
 
procedure TGraf.PridajHranu(C1, C2: Integer; V: TVaha);
begin
  if not JeHrana(C1, C2) then
    G[C1].PridajHranu(C2, V)
  else
    ZmenVahuHrany(C1, C2, V);
  // pre neorientovany graf
  if not JeHrana(C2, C1) then
    G[C2].PridajHranu(C1, V)
  else
    ZmenVahuHrany(C2, C1, 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
  G[C1].ZrusHranu(C2);
  G[C2].ZrusHranu(C1);     // pre neorientovane grafy
end;
 
procedure TGraf.ZmenVahuHrany(C1, C2: Integer; V: TVaha);
begin
  G[C1].ZmenVahuHrany(C2, V);
end;
 
function TGraf.JeHrana(C1, C2: Integer): Boolean;
begin
  Result := (C1 <= High(G)) and (C2 <= High(G)) and G[C1].JeHrana(C2);
end;

Môžeme pridať metódy na 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 - 10, Y - 10, X + 10, Y + 10);
  C.TextOut(X - 5, Y - 7, Meno);
end;
 
procedure TGraf.Kresli(C: TCanvas);
var
  I, J, XX, YY: Integer;
begin
  C.FillRect(Rect(0, 0, 1000, 1000));
  for I := 0 to High(G) do
  begin
    for J := 0 to High(G[I].Sus) do
    begin
      with G[G[I].Sus[J].Cislo] do
      begin
        XX := X;
        YY := Y;
      end;
      C.MoveTo(G[I].X, G[I].Y);
      C.LineTo(XX, YY);
      C.TextOut((G[I].X+XX) div 2, (G[I].Y+YY) div 2, IntToStr(G[I].Sus[J].Vaha));
    end;
  end;
  for I := 0 to High(G) do
    G[I].Kresli(C);
end;

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

var
  Graf: TGraf;
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  Randomize;
  Graf := TGraf.Create;
  Graf.PridajVrchol('prvy', Random(600), Random(600));
  Graf.PridajVrchol('druhy', Random(600), Random(600));
  Graf.PridajVrchol('treti', Random(600), Random(600));
  Graf.PridajHranu(0, 1, 10);
  Graf.PridajHranu(0, 2, 20);
  Graf.PridajHranu(1, 2, 30);
  Graf.Kresli(Image1.Canvas);
end;

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

var
  Graf: TGraf;
  Pocet: Integer = 0;
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  Image1.Canvas.FillRect(Image1.ClientRect);
  Randomize;
  Graf := TGraf.Create;
end;
 
procedure TForm1.Image1MouseDown(...);
var
  I: Integer;
begin
  Graf.PridajVrchol(IntToStr(Pocet+1), X, Y);
  for I := 0 to Pocet-1 do
    if Random(Pocet+1) < 2 then
      Graf.PridajHranu(I, Pocet, Random(100));
  Graf.Kresli(Image1.Canvas);
  Inc(Pocet);
end;

Poznámky:

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

Ďalšie námety:

  • doplňte do všetkých tried korektné zrušenie objektu (destructor Destroy)
  • doplňte do definície grafu metódy, resp. vlastnosti (property) tak, aby sa pohodlnejšie pracovalo s existujúcimi vrcholmi a hranami (napr. N - počet vrcholov grafu)
  • 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. stupeň vrcholu)
  • pre daný graf zistite počet izolovaných vrcholov


späť | ďalej