čo sme sa doteraz naučili

• existujú rôzne reprezentácie grafov, graf vieme vytvoriť aj vykresliť do grafickej plochy
• štruktúru údajov strom vieme prechádzať algoritmami typu inorder, preorder, postorder

čo sa budeme dnes učiť

• základné najjednoduchšie algoritmy na prechádzanie vrcholov v grafe
• zistenie počtu komponentov grafu a tým aj súvislosť grafu
• nájdenie najkratšej cesty v grafe pomocou algoritmu do hĺbky

Prehľadávanie grafov

• Budeme riešiť úlohy, v ktorých budeme postupne prechádzať všetky vrcholy grafu
• prehľadávanie sa začne z nejakého (ľubovoľného) vrcholu
• každý vrchol navštívime maximálne raz a možno práve raz (závisí od aplikácie)
• Postupujeme dvoma spôsobmi:
• do hĺbky - podobne ako preorder v stromoch
• do šírky - ako po úrovniach v stromoch
• Zadefinujeme pomocné pole na prehľadávanie, v ktorom sa pamätá sa, či bol vrchol už navštívený - často to býva stavová premenná triedy TGraf:
• var visited:array[vrcholy] of boolean;
• môže sa robiť aj ako
• var visited:set of vrcholy;
• Procedúra spracuj(vrchol) - spracuje daný vrchol (napr. vypíše info-položku)

Algoritmus do hĺbky

procedure dohlbky(v1);
begin
  visited:=visited + [v1];
  spracuj(v1);
  for w := všetkých susedov v1 do
    if not (w in visited) then dohlbky(w)
end;

Budeme predpokladať, že máme definované metódy na zistenie hrany, zafarbenie vrcholu a hrany

type
  TGraf = class
    g:array of record
        x,y:integer;
        m:set of byte;
      end;
    visited:set of byte;    // množina navštívených vrcholov
    ...
  end;

function TGraf.jeHrana(v1,v2:integer):boolean;
begin
  Result:=v2 in g[v1].m;
end;

procedure TGraf.zafarbiVrchol(v1:integer; f:TColor);
begin
  c.Pen.Color:=f;
  with g[v1] do c.Ellipse(x-r,y-r,x+r,y+r);
end;

procedure TGraf.zafarbiHranu(v1,v2:integer; f:TColor);
begin
  c.Pen.Color:=f;
  with g[v1] do c.MoveTo(x,y);
  with g[v2] do c.LineTo(x,y);
end;

type
  THrana = class
    cislo:integer;
    constructor Create(v:integer);
  end;

  TVrchol = class
    x,y:integer;
    sus:array of THrana;
  end;

  TGraf = class
    g:array of TVrchol;
    visited:set of byte;
    ...
  end;

function TGraf.jeHrana(v1,v2:integer):boolean;
var
  i:integer;
begin
  i:=high(g[v1].sus); while (i>=0) and (g[v1].sus[i].cislo<>v2) do dec(i);
  Result:=i>=0;
end;

...

A teraz konkrétne algoritmus prehľadávania do hĺbky

procedure TGraf.dohlbky(v1:integer);
var
  i:integer;
begin
  visited:=visited+[v1];
  zafarbiVrchol(v1,clRed);              // spracuj vrchol
  for i:=0 to high(g) do
    if not (i in visited) and jeHrana(v1,i) then begin
      zafarbiHranu(v1,i,clRed);         // spracuj hranu
      dohlbky(i);
    end;
end;

Otestujme tento algoritmus na takomto grafe:

Nerekurzívny algoritmus, ktorý iba do množiny navštívených vrcholov pridá všetky tie, ktoré sú dosiahnuteľné z nejakého počiatočného vrcholu:

procedure TGraf.dohlbky(v1:integer);
var
  i:integer;
  s:TStack;
begin
  s:=TStack.Create; s.push(v1);
  repeat
    s.pop(v1);
    visited:=visited+[v1];
    for i:=0 to high(g) do
      if not (i in visited) and jeHrana(v1,i) then
        s.push(i);
  until s.empty;
  s.Free;
end;

Hoci tento algoritmus vyzerá v poriadku, ak ho otestujeme na rovnakom jednoduchom grafe, zistíme, že niektorý vrchol sa bude spracovávať (zafarbovať) dvakrát a to môže byť v niektorých situáciách neprijateľné:

• opäť začneme s vrcholom 1: najprv sa vloží do prázdneho zásobníka, na začiatku repeat-cyklu sa vyberie a spracuje - zaeviduje (a možno aj zafarbí)
• vo for-cykle sa do teraz prázdneho zásobníka vložia susedia 1, t.j. do zásobníka pribudnú (2,3)
• na začiatku repeat-cyklu sa z vrchu zásobníka vyberie 3, zaeviduje a všetky ešte nenavštívené vrcholy, s ktorými susedí, sa pridajú do zásobníka - do zásobníka pribudne 4, t.j. je tam (2,4)
• z vrchu zásobníka sa vyberie 4, zaeviduje sa a vložia sa na vrch zásobníka nenavštívení susedia 4, t.j. v zásobníku teraz bude (2,2,5) - vidíme, že do zásobníka sa mohol dostať nenavštívený vrchol aj viackrát, preto treba tento algoritmus opraviť

procedure TGraf.dohlbky(v1:integer);
var
  i:integer;
  s:TStack;
begin
  s:=TStack.Create; s.push(v1);
  repeat
    s.pop(v1);
    if not (v1 in visited) then begin
      visited:=visited+[v1];
      for i:=0 to high(g) do
        if not (i in visited) and jeHrana(v1,i) then
          s.push(i);
    end;
  until s.empty;
  s.Free;
end;

Ďalší variant prehľadávania do hĺbky zafarbí danou farbou (parameter f) všetky vrcholy aj všetky hrany nejakého komponentu:

procedure TGraf.dohlbky(v1:integer; f:TColor);
var
  i:integer;
  s:TStack;
begin
  s:=TStack.Create; s.push(v1);
  repeat
    s.pop(v1);
    if not (v1 in visited) then begin
      visited:=visited+[v1];
      zafarbiVrchol(v1,f);
      for i:=0 to high(g) do
        if jeHrana(v1,i) then begin
          zafarbiHranu(v1,i,f);
          if not (i in visited) then s.push(i);
        end;
    end;
  until s.empty;
  s.Free;
end;

Pozn.

• Zrejme pred každým volaním algoritmu dohlbky by bolo treba nejako nastaviť množinu navštívených vrcholov - visited na prázdnu

algoritmus do hĺbky môžeme použiť na:

• zistenie počtu komponentov grafu, resp. či je graf súvislý
• nájdenie nejakej cesty medzi dvoma vrcholmi
• zistenie, či sú dva vrcholy v tom istom komponente
• zafarbovanie vrcholov a hrán

Nasledujúca metóda pomocou algoritmu do hĺbky (rekurzívneho alebo nerekurzívneho) zistí počet komponentov grafu - používa preddefinované pole nejakých farieb - príslušný prvok tohto poľa posiela do metódy dohlbky, ktorá touto farbou zafarbí daný podgraf (zrejme, môžeme použiť aj metódu dohlbky bez zafarbovania vrcholov a hrán):

const
  f:array[0..max] of TColor = (...);

function TGraf.komponenty:integer;
var
  i:integer;
begin
  Result:=0; visited:=[];
  for i:=0 to high(g) do
    if not (i in visited) then begin
      dohlbky(i,f[Result]);
      inc(Result);
    end;
end;

Algoritmus do šírky

Pri prehľadávaní stromu do šírky (po úrovniach) sme potrebovali rad (front).  Podobne budeme postupovať aj pri algoritme pre graf:

procedure dosirky(v1);
var
  q:TQueue;
  w:integer;
begin
  q:=TQueue.Create; q.append(v1);
  repeat
    q.serve(v1);
    if not (v1 in visited) then begin
      visited:=visited + [v1];
      spracuj(v1);
      for w := všetkých susedov v1 do
      // for w:=0 to high(g) do if jeHrana(v1,w) then
        if not (w in visited) then
          q.append(w)
    end;
  until q.empty;
  q.Free;
end;

Konkrétne použijeme algoritmus prehľadávania do šírky na zafarbovanie vrcholov podľa toho, ako ďaleko sú od počiatočného vrcholu v1:

procedure TGraf.dosirky(v1:integer);
var
  i,u:integer;
  q:TQueue;   // vo fronte si pre každý vrchol pamätáme jeho úroveň - vzdialenosť
begin
  q:=TQueue.Create; q.append(v1,0); visited:=[];
  repeat
    q.serve(v1,u);
    if not (v1 in visited) then begin
      visited:=visited+[v1];
      zafarbiVrchol(v1,f[u]);  // f je nejaké pole farieb
      for i:=0 to high(g) do
        if not (i in visited) and jeHrana(v1,i) then
          q.append(i,u+1);
    end;
  until q.empty;
  q.Free;
end;

Pozn.

• porovnajte tento algoritmus s nerekurzívnym prehľadávaním do hĺbky
• používame rad, do ktorého vkladáme aj vyberáme vždy dve celočíselné hodnoty
• v súbore graf.zip je jednoduchý ukážkový projekt s algoritmom do šírky

procedure TGraf.dosirky(v1:integer);
var
  i,u:integer;
  q:TQueue;
begin
  q:=TQueue.Create; q.append(v1,0); visited:=[];
  repeat
    q.serve(v1,u);
    if not (v1 in visited) then begin
      visited:=visited+[v1];
      for i:=0 to high(g) do
        if not (i in visited) and jeHrana(v1,i) then begin
          zafarbiHranu(v1,i,f[u]);
          q.append(i,u+1);
        end;
    end;
  until q.empty;
  q.Free;
end;

• hrany, ktoré majú od daného vrcholu rovnakú vzdialenosť (dĺžku cesty), sú zafarbené rovnakou farbou

function TGraf.vzdialenost(v1,v2:integer):integer;
var
  i,u:integer;
  q:TQueue;
begin
  Result:=-1; q:=TQueue.Create; q.append(v1,0); visited:=[];
  try
    repeat
      q.serve(v1,u);
      if not (v1 in visited) then begin
        if v1=v2 then begin Result:=u; exit; end;
        visited:=visited+[v1];
        for i:=0 to high(g) do
          if not (i in visited) and jeHrana(v1,i) then
            q.append(i,u+1);
      end;
    until q.empty;
  finally
    q.Free;
  end;
end;

• funkcia vráti -1, ak neexistuje cesta z v1 do v2

Rozšírime tento algoritmus nielen na zistenie vzdialenosti dvoch vrcholov, ale aj na zapamätanie tejto najkratšej cesty. Použijeme takúto ideu: vytvoríme pomocné pole, v ktorom si budeme pre každý vrchol pamätať jeho predchodcu v ceste, t.j. vždy, keď si v rade zapamätáme vrchol (append), ktorý plánujeme v budúcnosti preskúmať, zapamätáme si s ním aj jeho predchodcu (odkiaľ sme k nemu prišli). Keď vrchol z frontu vyberieme (serve), tak vieme aj jeho predchodcu na ceste a môžeme si ho zaevidovať v pomocnom poli. Na záver, keď sme dorazili do cieľa, pomocou predchodcov uložených v pomocnom poli sa vieme postupne vracať späť a teda vieme skonštruovať výsledné dynamické pole (hodnota -1 v poli znamená, že vrchol nemá predchodcu - je prvý na ceste).

type
  postupnost = array of integer;
...

function TGraf.najkratsiaCesta(v1,v2:integer):postupnost;
var
  i,v0:integer;
  q:TQueue;
  p:postupnost;
begin
  Result:=nil; SetLength(p,Length(g)); visited:=[];
  for i:=0 to high(p) do p[i]:=-1;
  q:=TQueue.Create; q.append(v1,-1);
  try
    repeat
      q.serve(v1,v0);
      if not (v1 in visited) then begin
        p[v1]:=v0;
        if v1=v2 then begin
          i:=0; repeat inc(i); v2:=p[v2] until v2<0;  // zistíme dĺžku cesty
          SetLength(Result,i);                        // pripravíme výsledné pole
          repeat dec(i); Result[i]:=v1; v1:=p[v1] until v1<0;  // prekopírujeme
          exit;    // try - finally zabezpečí, že sa vykoná q.Free;
        end;
        visited:=visited+[v1];
        for i:=0 to high(g) do
          if not (i in visited) and jeHrana(v1,i) then
            q.append(i,v1);
      end;
    until q.empty;
  finally
    q.Free;
  end;
end;

Pozn.

• high(najkratsiaCesta(v1,v2)) - vráti dĺžku cesty

zhrňme použitie algoritmu do šírky:

• podobne ako do hĺbky, vieme zistiť vrcholy, ktoré patria do jedného komponentu a teda aj zistiť počet komponentov
• vieme zistiť (zafarbiť) vrcholy/hrany rovnako vzdialené od daného vrcholu
• vieme zistiť vzdialenosť, resp. najkratšiu cestu medzi dvoma vrcholmi v grafe

NDÚ:

• odlaďte tieto algoritmy v rôznych reprezentáciách grafu
• zrealizujte prevody medzi rôznymi reprezentáciami grafov, napr. graf reprezentovaný poľom množín prekonvertujte do dynamického poľa dynamických polí
• prevod binárneho/N-árneho/všeobecného stromu do orientovaného/neorientovaného grafu
• vygenerovať graf, napr. šachovnicu NxN:
• vrcholy sú susedné podľa pohybu kráľa/koňa/...