32.Prednaska

Z Pascal
Prejsť na: navigácia, hľadanie
32. Prednáška
úlohy | cvičenie


Generovanie grafu

Aby sme mohli testovať rôzne spôsoby prehľadávania grafov, vytvoríme triedu TGraf, ktorá okrem štandardných metód (pridávanie vrcholu a hrany, zisťovanie, či je medzi dvoma vrcholmi hrana) bude obsahovať aj metódy na nakreslenie grafu, resp. zafarbenie vrcholu a hrany. Napr. pre graf reprezentovaný poľom množín (môžete použiť tento pripravený projekt): 

type
  TVrchol = class
  private
    X, Y: Integer;
    Sus: set of Byte;          // množina susedov
  public
    constructor Create(XX, YY: Integer);
    procedure Kresli(C: TCanvas);
    function Vzd(XX, YY: Integer): Integer;
  end;
 
  TGraf = class
    Image: TImage;
    G: array of TVrchol;
    constructor Create(II: TImage);
    procedure PridajVrchol(XX, YY: Integer);
    procedure PridajHranu(V1, V2: Integer);
    function JeHrana(V1, V2: Integer): Boolean;
    procedure ZafarbiVrchol(V1: Integer; Farba: TColor);
    procedure ZafarbiHranu(V1, V2: Integer; Farba: TColor);
    procedure Kresli;
  end;

Niektoré metódy potom môžu vyzerať takto: 

function TGraf.JeHrana(V1, V2: Integer): Boolean;
begin
  Result := V2 in G[V1].Sus;
end;
 
procedure TGraf.ZafarbiVrchol(V1: Integer; Farba: TColor);
begin
  with Image.Canvas do
  begin
    Pen.Color := Farba;
    Brush.Color := Farba;
    Brush.Style := bsSolid;
    G[V1].Kresli(Image.Canvas);
    Brush.Style := bsClear;
  end;
end;
 
procedure TGraf.ZafarbiHranu(V1, V2: Integer; Farba: TColor);
begin
  with Image.Canvas do
  begin
    Pen.Color := Farba;
    Line(G[V1].X, G[V1].Y, G[V2].X, G[V2].Y);
  end;
end;
 
procedure TGraf.Kresli;
var
  I, J: Integer;
begin
  with Image.Canvas do
  begin
    Brush.Color := clWhite;
    Brush.Style := bsSolid;
    FillRect(Image.ClientRect);
    Pen.Width := 3;
  end;
  for I := 0 to High(G) do
  begin
    ZafarbiVrchol(I, clLtGray);
    for J := 0 to High(G) do
      if JeHrana(I, J) then
        ZafarbiHranu(I, J, clLtGray);
  end;
end;

Teraz môžeme zostaviť aplikáciu, ktorá vygeneruje graf s 10 náhodne položenými vrcholmi. Program tiež náhodne pospája niektoré vrcholy grafu hranami. Inštanciu Graf triedy TGraf zadeklarujeme ako globálnu premennú: 

var
 Graf: TGraf;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  I, J: Integer;
begin
  Graf.Free;
  Graf := TGraf.Create(Image1);
  for I := 1 to 10 do
  begin
    Graf.PridajVrchol(Random(Image1.Width), Random(Image1.Height));
    for J := 0 to High(Graf.G) - 1 do
      if Random(4) = 0 then
        Graf.PridajHranu(High(Graf.G), J);
  end;
  Graf.Kresli;
end;

Takto vygenerovaný graf je ale veľmi neprehľadný. Graf budeme preto generovať tak, že vrcholy rovnomerne rozložíme vo štvorcovej sieti. Do formulára vložíme aj komponent vstupný riadok Edit1 (veľkosť siete), do ktorého môžeme vkladať rôzne číselné hodnoty a tým generovať rôzne veľké grafy: 

procedure TForm1.Button2Click(Sender: TObject);
var
  I, J, N, D: Integer;
begin
  Graf.Free;
  Graf := TGraf.Create(Image1);
 
  N := StrToIntDef(Edit1.Text, 4);
  D := Image1.Width div (N + 2);
  for I := 0 to N - 1 do
    for J := 0 to N - 1 do
    begin
      Graf.PridajVrchol(D * J + D, D * I + D);
      if (Random(4) > 0) and (J > 0) then
        Graf.PridajHranu(High(Graf.G), High(Graf.G) - 1);
      if (Random(4) > 0) and (I > 0) then
        Graf.PridajHranu(High(Graf.G), High(Graf.G) - N);
    end;
  Graf.Kresli;
end;

Nakoľko táto reprezentácia grafu (pole množín) umožňuje pracovať s grafom, ktorý má maximálne 256 vrcholov. Ak zadáme väčšiu veľkosť siete ako 16x16, vygeneruje sa len 256 vrcholov.


Algoritmus do hĺbky

Prehľadávanie grafu znamená taký algoritmus, ktorý postupne prechádza vrcholy grafu. S každým vrcholom pritom vykoná nejakú akciu (napr. ho zafarbí) a ďalej pokračuje na niektorom z jeho susedných vrcholov. 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í to od zadania úlohy).

Ukážeme dva základné algoritmy:

  • prehľadávanie do hĺbky - funguje podobne ako preorder na stromoch: najprv spracuje vrchol a potom postupne pokračuje v prehľadávaní všetkých svojich susedov - opäť rekurzívnym algoritmom
  • prehľadávanie do šírky - prehľadáva vrcholy podobne ako prehľadávanie vrcholov po úrovniach v stromoch - najprv všetky, ktoré majú vzdialenosť len 1, potom všetky, ktoré majú vzdialenosť presne 2, atď.

Pri prehľadávaní grafu pomocou nejakého algoritmu si potrebujeme evidovať, ktoré vrcholy sa už spracovali. Keďže samotný algoritmus môže byť rekurzívny, túto evidenciu nemôžeme robiť v lokálnej premennej samotnej procedúry - môže to byť buď globálna premenná, alebo stavová premenná triedy TGraf: 

Visited: array of Boolean;

alebo pre grafy do 256 vrcholov aj ako 

Visited: set of Byte;

Ak je každý vrchol objektom (napr. TVrchol), tak sem môžeme dodefinivať novú stavovú premennú (namiesto poľa alebo množiny Visited): 

Visited: Boolean;

Najprv zapíšeme algoritmus do hĺbky všeobecne: prehľadávanie, ak začíname vo vrchole V: 

procedure Dohlbky(V);
begin
  Visited := Visited + [V];
  // spracovanie vrcholu V
  for I := všetkých susedov V do
    if not (I in Visited) then
      Dohlbky(I);
end;

A teraz konkrétne algoritmus prehľadávania do hĺbky - zafarbuje navštívené vrcholy aj hrany, po ktorých algoritmus prechádza. Najprv vytvoríme obyčajnú procedúru, ktorá sa spúšťa pri zatlačení tlačidla: 

procedure TForm1.Button3Click(Sender: TObject);
var
  Visited: set of Byte;
 
  procedure Dohlbky(V: Integer);
  var
    I: Integer;
  begin
    Visited := Visited + [V];
    // spracuj vrchol
    Graf.ZafarbiVrchol(V, clRed);
    for I := 0 to High(Graf.G) do
      if not (I in Visited) and Graf.JeHrana(V, I) then
      begin
        Graf.ZafarbiHranu(V, I, clRed);
        Graf.Wait(100);
        Dohlbky(I);
      end;
  end;
 
begin
  Visited := [];
  Graf.Kresli;
  Dohlbky(0);
end;

Môžete vidieť, že premenná Visited je globálna voči samotnej procedúre Dohlbky.

Teraz zapíšeme to isté, ale ako metódu triedy TGraf. Premenná Visited musí byť teraz stavovou premennou (atribútom) triedy TGraf: 

type
  TGraf = class
    Visited: set of Byte;
    ...
    procedure Dohlbky(V: Integer);
  end;
 
procedure TGraf.Dohlbky(V: Integer);
var
  I: Integer;
begin
  Visited := Visited + [V];
  ZafarbiVrchol(V, clRed);              // spracuj vrchol
  for I := 0 to High(G) do
    if not (I in Visited) and JeHrana(V, I) then
    begin
      ZafarbiHranu(V, I, clRed);         // spracuj hranu
      // Wait(50);
      Dohlbky(I);
    end;
end;

Prepíšeme aj procedúru TForm1.Button3Click: 

procedure TForm1.Button3Click(Sender: TObject);
begin
  Graf.Visited := [];
  Graf.Kresli;
  Graf.Dohlbky(0);
  if Graf.Visited = [0..High(Graf.G)] then
    Image1.Canvas.TextOut(5, 5, 'graf je súvislý')
  else
    Image1.Canvas.TextOut(5, 5, 'graf nie je súvislý');
end;

Treba si uvedomiť, že po skončení algoritmu Dohlbky bude premenná Visited obsahovať množinu všetkých navštívených vrcholov. Na základe toho, môžeme usúdiť, či je graf súvislý - ak táto množina obsahuje všetky vrcholy grafu, tento graf je súvislý, inak (niektoré vrcholy sa nepodarilo dosiahnuť) je nesúvislý.


Komponenty grafu

Farbenie komponentov grafu


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

procedure TGraf.Dohlbky(V: Integer; Farba: TColor);
var
  I: Integer;
begin
  Visited := Visited + [V];
  ZafarbiVrchol(V, Farba);
  Wait(10);
  for I := 0 to High(G) do
    if JeHrana(V, I) then
    begin
      ZafarbiHranu(V, I, Farba);
      if not (I in Visited) then
        Dohlbky(I, Farba);
    end;
end;

Túto verziu prechádzania grafu algoritmom do hĺbky môžeme otestovať takto: 

procedure TForm1.Button4Click(Sender: TObject);
const
  Farba: array[0..10] of TColor =
    (clRed, clBlue, clGreen, clBlack, clYellow, clNavy,
     clTeal, clLime, clAqua, clFuchsia, clOlive);
var
  N, I: Integer;
begin
  N := 0;
  Graf.Visited := [];
  Graf.Kresli;
  for I := 0 to High(Graf.G) do
    if not (I in Graf.Visited) then
    begin
      Graf.Dohlbky(I, Farba[N]);
      Inc(N);
    end;
  Image1.Canvas.TextOut(5, 5, 'počet komponentov = ' + IntToStr(N));
end;



Počet komponentov grafu


Nasledujúca metóda pomocou algoritmu do hĺbky zistí počet komponentov grafu: 

function TGraf.PocetKomponentov: Integer;
var
  I: Integer;
begin
  Result := 0;
  Visited := [];
  for I := 0 to High(G) do
    if not (I in Visited) then
    begin
      Dohlbky(I);
      Inc(Result);
    end;
end;

Samotný algoritmus do hĺbky pre zisťovanie počtu komponentov teraz už nemusí nič zafarbovať - stačí len evidovať navštívené vrcholy v premennej Visited, napr. 

procedure TGraf.Dohlbky(V: Integer);
var
  I: Integer;
begin
  Visited := Visited + [V];
  for I := 0 to High(G) do
    if not (I in Visited) and JeHrana(V, I) then
      Dohlbky(I);
end;

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

  • zistenie počtu komponentov grafu, resp. zisťovanie, či je graf súvislý
  • zistenie, či sú dva vrcholy v tom istom komponente
  • zisťovanie počtov vrcholov v jednotlivých komponentoch grafu
  • zafarbovanie vrcholov a hrán jednotlivých komponentov grafu


Nerekurzívny algoritmus do hĺbky

Prepíšme teraz rekurzívny algoritmus Dohlbky na nerekurzívnu verziu. Využijeme pritom triedu zásobník z unitu StackUnit. Nerekurzívny algoritmus môže vyzerať takto: 

procedure TGraf.DohlbkyNR(V: Integer);
var
  Stack: TStack;
  I: Integer;
begin
  Stack := TStack.Create;
  Stack.Push(V);
  repeat
    Stack.Pop(V);
    Visited := Visited + [V];
    ZafarbiVrchol(V, clRed);          // spracuj vrchol
    for I := 0 to High(G) do
      if not (I in Visited) and JeHrana(V, I) then
        Stack.Push(I);
  until Stack.Empty;
  Stack.Free;
end;

Zrejme zásobník musí mať prvky typu Integer.

Hoci tento algoritmus vyzerá v poriadku, ak ho otestujeme na nejakom 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é. Ak by sme si algoritmus odtrasovali ručne, zistili by sme, že niektoré čísla vrcholov sa dostávajú do zásobníka viackrát (napr. vrchol, ktorý ešte nebol navštívený, ale je susedom viacerých už navštívených vrcholov). Jednoducho to môžeme preveriť aj tak, že do tohto algoritmu vložíme počítadlo zafarbených vrcholov a po skončení algoritmu porovnáme tento počet so skutočným počtom vrcholov komponentu. Napr. 

type
  TGraf = class
    Pocet: Integer;
    ...
    procedure DohlbkyNR(V: Integer);
  end;
 
procedure TGraf.DohlbkyNR(V: Integer);
var
  Stack: TStack;
  I: Integer;
begin
  Stack := TStack.Create;
  Stack.Push(V);
  repeat
    Stack.Pop(V);
    Visited := Visited + [V];
    ZafarbiVrchol(V, clRed);          // spracuj vrchol
    Inc(Pocet);
    for I := 0 to High(G) do
      if not (I in Visited) and JeHrana(V, I) then
        Stack.Push(I);
  until Stack.Empty;
  Stack.Free;
end;
 
procedure TForm1.Button3Click(Sender: TObject);
var
  I, N: Integer;
begin
  Graf.Visited := [];
  Graf.Kresli;
  Graf.Pocet := 0;
  Graf.DohlbkyNR(0);
  N := 0;
  for I in Visited do
    Inc(N);
  Image1.Canvas.TextOut(5, 5, 'Visited = ' + IntToStr(N));
  Image1.Canvas.TextOut(5, 25, 'Pocet = ' + IntToStr(Graf.Pocet));
end;

Správne by mal nerekurzívny algoritmus vyzerať takto: 

procedure TGraf.DohlbkyNR(V: Integer);
var
  Stack: TStack;
  I: Integer;
begin
  Stack := TStack.Create;
  Stack.Push(V);
  repeat
    Stack.Pop(V);
    if not (V in Visited) then
    begin
      Visited := Visited + [V];
      ZafarbiVrchol(V, clRed);
      for I := 0 to High(G) do
        if not (I in Visited) and JeHrana(V, I) then
          Stack.Push(I);
    end;
  until Stack.Empty;
  Stack.Free;
end;

Takýto nerekurzívny algoritmus použijeme napr. vtedy, keď z nejakého dôvodu nechceme v programe spúšťať rekurziu. Tento nerekurzívny algoritmus inak nemá žiadne špeciálne výhody - skôr naopak - je to komplikovanejší kód, pri ktorom ľahšie urobíme chybu.


Algoritmus do šírky

Ak by sme potrebovali prehľadávať napr. binárny strom po úrovniach (algoritmus do šírky), potrebovali by sme dátovú štruktúru rad (front alebo queue). Podobne budeme postupovať aj pri algoritme pre graf. Tento algoritmus sa bude od nerekurzívneho algoritmu do hĺbky líšiť len tým, že namiesto TStack použijeme TQueue (a teda aj premenujeme jeho metódy): 

procedure TGraf.Dosirky(V: Integer);
var
  Queue: TQueue;
  I: Integer;
begin
  Queue := TQueue.Create;
  Queue.Append(V);
  repeat
    Queue.Serve(V);
    if not (V in Visited) then
    begin
      Visited := Visited + [V];
      ZafarbiVrchol(V, clRed);
      for I := 0 to High(G) do
        if not (I in Visited) and JeHrana(V, I) then
          Queue.Append(I);
    end;
  until Queue.Empty;
  Queue.Free;
end;

Takto zapísaný algoritmus bude robiť skoro presne to isté ako nerekurzívny algoritmus do hĺbky. Rozdiel bud v tom, že sa v inom poradí navštívia všetky vrcholy grafu: najprv sa spracujú všetky najbližšie susediace vrcholy ku štartovému; potom sa spracujú všetci ich ešte nenavštívení susedia atď. Vďaka tejto vlastnosti algoritmu ho môžeme veľmi jednoducho vylepšiť: pri každom spracovávanom vrchole si budeme pamätať aj jeho momentálnu vzdialenosť - teda úroven "vnorenia". Štartový vrchol prehľadávania bude mať úroveň 0, všetci jeho bezprostrední susedia budú mať úroveň 1 a každý ďalší vrchol bude mať úroveň o 1 väčšiu ako vrchol, od ktorého sa sem prišlo.

Program prepíšeme tak, že vo fronte si budeme pri každom vrchole pamätať aj jeho úroveň v premennej Uroven. Použijeme dátovú štruktúru TQueue definovanú v unite QueueUnit (používa rad, do ktorého vkladáme aj vyberáme vždy dve celočíselné hodnoty). 

procedure TGraf.Dosirky(V: Integer);
var
  I, Uroven: Integer;
  Queue: TQueue;
begin
  Queue := TQueue.Create;
  Queue.Append(V, 0);
  repeat
    Queue.Serve(V, Uroven);
    Wait(1);
    if not (V in Visited) then
    begin
      Visited := Visited + [V];
      ZafarbiVrchol(V, clRed);
      Image.Canvas.TextOut(G[V].X, G[V].Y, IntToStr(Uroven));
      for I := 0 to High(G) do
        if not (I in Visited) and JeHrana(V, I) then
          Queue.Append(I, Uroven + 1);
    end;
  until Queue.Empty;
  Queue.Free;
end;

Všimnite si, že program teraz pri každom navštívenom vrchole vypíše aj jeho vzdialenosť (úroveň) od štartového vrcholu.

Algoritmus do šírky môžeme otestovať tak, že pri kliknutí do grafickej plochy na niektorý vrchol, sa z tohto miesta naštartuje prehľadávanie do šírky: 

procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
var
  I: Integer;
begin
  I := High(Graf.G);
  while (I >= 0) and (Graf.G[I].Vzd(X, Y) > 30) do
    Dec(I);
  if I >= 0 then
  begin
    Graf.Visited := [];
    Graf.Dosirky(I);
  end
  else
    Graf.Kresli;
end;

V tomto programe sme využili metódu Vzd, ktorá počíta vzdialenosť nakresleného vrcholu od ľubovoľného bodu (X, Y) v grafickej ploche.


Vzdialenosť a najkratšia cesta

Vzdialenosť dvoch vrcholov


Algoritmus do šírky môžeme využiť aj na zisťovanie vzdialenosti ľubovoľných dvoch vrcholov v grafe. Pod vzdialenosťou tu rozumieme dĺžku najkratšej cesty z jedného vrcholu do druhého. Ak takáto cesta neexistuje (vrcholy sú v rôznych komponentoch grafu), metóda vráti hodnotu -1: 

function TGraf.Vzdialenost(V1, V2: Integer): Integer;
var
  I, Uroven: Integer;
  Queue: TQueue;
begin
  Visited := [];
  Queue := TQueue.Create;
  Queue.Append(V1, 0);
  Result := -1;
  repeat
    Queue.Serve(V1, Uroven);
    if not (V1 in Visited) then
    begin
      Visited := Visited + [V1];
      if V1 = V2 then
      begin
        Result := Uroven;
        Break;
      end;
      for I := 0 to High(G) do
        if not (I in Visited) and JeHrana(V1, I) then
          Queue.Append(I, Uroven + 1);
    end;
  until Queue.Empty;
  Queue.Free;
end;



Najkratšia cesta v grafe


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

Algoritmus hľadania najkratšej cesty v grafe: 

type
  TPostupnost = array of Integer;
...
 
function TGraf.NajkratsiaCesta(V1, V2: Integer): TPostupnost;
var
  I, V0: Integer;
  Queue: TQueue;
  P: TPostupnost;
begin
  Result := nil;
  SetLength(P, Length(G));
  Visited := [];
  for I := 0 to High(P) do
    P[I] := -1;
  Queue := TQueue.Create;
  Queue.Append(V1, -1);
  repeat
    Queue.Serve(V1, V0);
    if not (V1 in Visited) then
    begin
      P[V1] := V0;
      if V1 = V2 then
      begin
        I := 0;
        repeat                   // zistíme dĺžku cesty
          Inc(I);
          V2 := P[V2];
        until V2 < 0;
        SetLength(Result, I);    // pripravíme výsledné pole
        repeat                   // prekopírujeme
          Dec(I);
          Result[I] := V1;
          V1 := P[V1];
        until V1 < 0;
        Break;
      end;
      Visited := Visited + [V1];
      for I := 0 to High(G) do
        if not (I in Visited) and JeHrana(V1, I) then
          Queue.Append(I, V1);
    end;
  until Queue.Empty;
  Queue.Free;
end;

Otestovať tento algoritmus môžeme opäť klikaním do grafickej plochy: prvé kliknutie (ľavým tlačidlom myši) na nejaký vrchol tento vrchol označí a potom klikania na ďalšie vrcholy (pravým tlačidlom, alebo ľavým so zatlačeným klávesom Ctrl) vykreslia najkratšiu cestu: 

var
  Start: Integer = -1;
 
procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
var
  I: Integer;
  P: TPostupnost;
begin
  I := High(Graf.G);
  while (I >= 0) and (Graf.G[I].Vzd(X, Y) > 30) do
    Dec(I);
  if I < 0 then
    Exit;
  Graf.Kresli;
  if Shift = [ssLeft] then
  begin
    Start := I;
    Graf.ZafarbiVrchol(Start, clRed);
  end
  else if Start >= 0 then
  begin
    P := Graf.NajkratsiaCesta(Start, I);
    for I := 1 to High(P) do
      Graf.ZafarbiHranu(P[I - 1], P[I], clBlue);
    Graf.ZafarbiVrchol(Start, clRed);
  end;
end;

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 (alebo hrany), ktoré sú rovnako vzdialené od daného vrcholu
  • vieme zistiť vzdialenosť, resp. najkratšiu cestu medzi dvoma vrcholmi v grafe
  • napr. pomocou High(NajkratsiaCesta(V1, V2)) vieme zistiť vzdialenosť dvoch vrcholov v grafe


späť | ďalej
Zdroj: „http://pascal.input.sk/index.php?title=32.Prednaska&oldid=1406“