32.Prednaska/Cvicenie0

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

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