32.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
 
Riadok 32: Riadok 32:
  
 
<!-- -->
 
<!-- -->
 
=== 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;
 
var
 
  Stupen: Integer;
 
  I:
 
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
 
end;
 
 
 
<!-- -->
 
 
{{Podnadpis|Ď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ý)
 

Aktuálna revízia z 12:14, 15. máj 2013

32. Cvičenie


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


Rozcvička

1. napíšte funkciu, ktorá pre neorientovaný graf:

type
  TGraf = class
    G: array [1..N,1..N] of Boolean;
  end;
 
function TGraf.PocetIzolovanych: Integer;
  • zistí počet izolovaných vrcholov

2. napíšte funkciu, ktorá pre graf:

type
  TGraf = class
    G: array [1..N,1..N] of Boolean;   // alebo G: array of set of Byte;
  end;
 
function TGraf.JeOrientovany: Boolean;
  • zistí, či je graf orientovaný