32.Prednaska/Cvicenie

Z Pascal
Prejsť na: navigácia, hľadanie

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