32.Prednaska/Cvicenie

32. Cvičenie

---

< 32.Prednáška | riešené úlohy

Cvičenie

• pre rôzne grafy (okolo 12 vrcholov, domček, stromček, labyrint v štvorcovej sieti(vrcholy sú políčka a hrana je tam, kde nieje stena), viackomponentový graf)

• najprv ručne na tabuli:

• do hĺbky - vidíte istú podobnosť s preorder?

dohlbky(v)
  vis := vis + (v)
  spracuj(v)
  for susedia(v)
    if not visited
      dohlbky(u)

• písať si poradie navštívenia vrcholov ak začíname z nejakého
• na viackomponentovom ukázať, že algoritmus do hĺbky nám zistí ktoré vrcholy sú spojené - zistí komponenty

• do šírky - na všetkých grafoch

• pripomenúť si ako funguje, vypísať si poradie navštívenia vrcholov
• spomenúť, že nám nájde najkratšiu cestu - dá sa zrekonštruovať z postupnosti prechádzania vrcholov, alebo písaním vzdialenosti od štartu do vrcholov

• vzdialenosť/cestu medzi dvoma vrcholmi

• grafové algoritmy na štruktúre, vrcholy sú číslované od 0 po N-1

TGraf = class
  G: array of set of Byte;
  Visited: set of Byte;
end;

• otestovať či je medzi dvoma vrcholmi hrana TGraf.JeHrana(A, B: Integer): Boolean

function TGraf.JeHrana(A, B: Integer): Boolean;
begin
  Result := A in G[B];
end;

• prehľadávanie do hĺbky z daného vrcholu TGraf.DoHlbky(V: Integer);

procedure TGraf.DoHlbky(V: Integer);
var I: Integer
begin
  Visited := Visited + [V];
  Write(V, ' ');
  for I in G[V] do
    if not (I in Visited) then
      DoHlbky(I);
end;

• stupeň daného vrcholu, tj. zistiť počet susedov TGraf.Stupen(V: Integer): Integer

function TGraf.Stupen(V: Integer): Integer;
begin
  Result := 0;
  for I in G[V] do
    Inc(Result);
end;

• počet izolovaných vrcholov v grafe, tj. vrcholov ktoré so žiadnymi nesusedia TGraf.PocetIzolovanych: Integer

function TGraf.PocetIzolovanych: Integer;
var
  Stupen: Integer;
  I: Integer;
begin
  Result := 0;
  for I := 0 to High(G) do
    if Stupen(I) = 0 then
      Inc(Result);
end;

• maximálny stupeň vrchola v grafe TGraf.MaxStupen: Integer

function TGraf.MaxStupen: Integer;
var
  Stupen: Integer;
  I: Integer;
begin
  Result := 0;
  for I := 0 to High(G) do
    if Stupen(I) > Result then
      Result := Stupen(I);
end;

• upraviť, aby sa stupeň volal iba raz

...

• test súvislosti grafu TGraf.JeSuvisly: Boolean

• prehľadať a skontrolovať, či sme navštívili každý vrchol

function TGraf.JeSuvisly: Boolean;
begin
  Visited := [];
  DoHlbky(0);
  if Visited = [0..High(G)] then
    Result := True;
  else
    Result := False;
end;

• test súvislosti po odobraní daného vrcholu TGraf.Rozpad(V: Integer): Boolean

• predpokladáme, že na začiatku je graf súvislý
• označiť V ako navštívený, prehľadať z ľubovoľného iného vrchola a skontrolovať, či sme navštívili každý vrchol

function TGraf.Rozpad(V: Integer): Boolean;
begin
  Visited := [V];
  DoHlbky(Ord(V = 0));    // trik, aby začal z vrcholu iného ako V
  if Visited = [0..High(G)] then
    Result := True;
  else
    Result := False;
end;

• prehľadávanie do šírky bez Queue ale pomocou pomocného dynamického poľa TGraf.DoSirky(V: Integer)

• kde je miesto, kam dať výpis čísla vrchola, aby sme dostali usporiadanie vrcholov v poradí prechádzania?

procedure TGraf.DoSirky(V: Integer);
var
  K: array of Integer;
  I: Integer;
begin
  SetLength(K, 1);
  K[0] := V;
  repeat
    V := K[0];
    if length(K) = 1 then
      K := nil
    else
      K := Copy(K, 1, MaxInt);
    if not (V in Visited) then
    begin
      // tuto je miesto, kde by sa vypisoval vrchol
      Visited := Visited + [V];
      for I in G[V] do
        if not (I in Visited) then
        begin
          SetLength(K, Length(K) + 1);
          K[High(K)] := I;
        end;
    end;
  until K = nil;
end;

Ďalšie námety

---

• vrchol s najmenším/najväčším stupňom
• veľkosť komponentu, ktorý obsahuje vrchol V
• počet komponentov
• najväčší komponent

Domáca úloha

1. naprogramovať podprogram, ktorý do neorientovaného grafu pridá novú neorientovanú hranu tak, že sa vďaka tomu zníži počet komponentov:

function TGraf.PridajHranu: Boolean;

• vráti False, ak sa už hrana pridať nedala (graf bol už súvislý)