32.Prednaska/Cvicenie: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
Riadok 27: Riadok 27:
 
* grafové algoritmy na štruktúre, vrcholy sú číslované od 0 po N-1
 
* grafové algoritmy na štruktúre, vrcholy sú číslované od 0 po N-1
 
  TGraf = class
 
  TGraf = class
   G: array of set of byte;
+
   G: array of set of Byte;
   visited: set of byte;
+
   Visited: set of Byte;
 
  end;
 
  end;
  
Riadok 34: Riadok 34:
 
  function TGraf.JeHrana(A, B: Integer): Boolean;
 
  function TGraf.JeHrana(A, B: Integer): Boolean;
 
  begin
 
  begin
   result := A in G[B];
+
   Result := A in G[B];
 
  end;
 
  end;
  
 
* prehľadávanie do hĺbky z daného vrcholu '''TGraf.DoHlbky(V: Integer);'''
 
* prehľadávanie do hĺbky z daného vrcholu '''TGraf.DoHlbky(V: Integer);'''
 
  procedure TGraf.DoHlbky(V: Integer);
 
  procedure TGraf.DoHlbky(V: Integer);
  var I:Integer
+
  var I: Integer
 
  begin
 
  begin
   visited := visited + [V];
+
   Visited := Visited + [V];
   Write(V,' ');
+
   Write(V, ' ');
 
   for I in G[V] do
 
   for I in G[V] do
     if not (I in visited) then
+
     if not (I in Visited) then
 
       DoHlbky(I);
 
       DoHlbky(I);
 
  end;
 
  end;
Riadok 52: Riadok 52:
 
  begin
 
  begin
 
   Result := 0;
 
   Result := 0;
   for i in G[V] do
+
   for I in G[V] do
 
     inc(Result);
 
     inc(Result);
 
  end;
 
  end;
Riadok 79: Riadok 79:
 
       Result := Stupen(I);
 
       Result := Stupen(I);
 
  end;
 
  end;
upraviť, aby sa stupeň volal iba raz
+
* upraviť, aby sa stupeň volal iba raz
 
  ...
 
  ...
  
Riadok 85: Riadok 85:
 
:* prehľadať a skontrolovať, či sme navštívili každý vrchol
 
:* prehľadať a skontrolovať, či sme navštívili každý vrchol
 
  function TGraf.JeSuvisly: Boolean;
 
  function TGraf.JeSuvisly: Boolean;
var
 
  Stupen: Integer;
 
  I:
 
 
  begin
 
  begin
   visited := [];
+
   Visited := [];
 
   DoHlbky(0);
 
   DoHlbky(0);
   if visited = [0..High(G)] then
+
   if Visited = [0..High(G)] then
 
     Result := True;
 
     Result := True;
 
   else
 
   else
Riadok 102: Riadok 99:
 
  function TGraf.Rozpad(V: Integer): Boolean;
 
  function TGraf.Rozpad(V: Integer): Boolean;
 
  begin
 
  begin
   visited := [V];
+
   Visited := [V];
 
   DoHlbky(Ord(V = 0));    ''// trik, aby začal z vrcholu iného ako V''
 
   DoHlbky(Ord(V = 0));    ''// trik, aby začal z vrcholu iného ako V''
 
   if Visited = [0..High(G)] then
 
   if Visited = [0..High(G)] then
Riadok 121: Riadok 118:
 
   repeat
 
   repeat
 
     V := K[0];
 
     V := K[0];
     if length(K) = 1 then K := nil;
+
     if length(K) = 1 then
      else K := Copy(K, 1, MaxInt);
+
      K := nil
     if not (V in visited) then
+
    else
 +
      K := Copy(K, 1, MaxInt);
 +
     if not (V in Visited) then
 
     begin
 
     begin
 
       ''// tuto je miesto, kde by sa vypisoval vrchol''
 
       ''// tuto je miesto, kde by sa vypisoval vrchol''
       visited := visited + [V];
+
       Visited := Visited + [V];
 
       for I in G[V] do
 
       for I in G[V] do
         if not (I in visited) then
+
         if not (I in Visited) then
 
         begin
 
         begin
 
           SetLength(K, Length(K) + 1);
 
           SetLength(K, Length(K) + 1);
Riadok 134: Riadok 133:
 
         end;
 
         end;
 
     end;
 
     end;
   until
+
   until K = nil;
 
  end;
 
  end;
 
   
 
   

Verzia zo dňa a času 12:12, 15. máj 2013

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