32.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
Riadok 36: Riadok 36:
  
  
pre rôzne grafy (okolo 12 vrcholov, alebo labyrint v štvorcovej sieti)
+
* 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: do hĺbky, do šírky, vzdialenosť/cestu medzi dvoma vrcholmi
+
 
* potom zapisovať algoritmy pre:
+
* najprv ručne na tabuli:  
** stupeň vrchola
+
:* do hĺbky - vidíte istú podobnosť s preorder?
** vrchol s najmenším/najväčším stupňom
+
dohlbky(v)
** veľkosť komponentu, ktorý obsahuje vrchol V
+
  vis := vis + (v)
** počet komponentov
+
  spracuj(v)
** najväčší komponent
+
  for susedia(v)
** do šírky bez Queue ale pomocou pomocného dynamického poľa
+
    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
  
  

Verzia zo dňa a času 11:25, 12. apríl 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ý


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;



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