32.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
Riadok 39: Riadok 39:
 
* najprv ručne: do hĺbky, do šírky, vzdialenosť/cestu medzi dvoma vrcholmi
 
* najprv ručne: do hĺbky, do šírky, vzdialenosť/cestu medzi dvoma vrcholmi
 
* potom zapisovať algoritmy pre:
 
* potom zapisovať algoritmy pre:
 +
** stupeň vrchola
 +
** vrchol s najmenším/najväčším stupňom
 
** veľkosť komponentu, ktorý obsahuje vrchol V
 
** veľkosť komponentu, ktorý obsahuje vrchol V
 
** počet komponentov
 
** počet komponentov

Verzia zo dňa a času 05:48, 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, alebo labyrint v štvorcovej sieti)

  • najprv ručne: do hĺbky, do šírky, vzdialenosť/cestu medzi dvoma vrcholmi
  • potom zapisovať algoritmy pre:
    • stupeň vrchola
    • vrchol s najmenším/najväčším stupňom
    • veľkosť komponentu, ktorý obsahuje vrchol V
    • počet komponentov
    • najväčší komponent
    • do šírky bez Queue ale pomocou pomocného dynamického poľa


Domáca úloha

1. naprogramovať podprogram, ktorý do grafu pridá pridá novú 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ý)