34.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Verzia zo dňa a času 09:57, 10. máj 2013

34. Cvičenie

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

Rozcvička

1. graf je zadeklarovaný:

type
  TVrchol = class
    Meno: Integer;
    Sus: set of 1..N;
  end;
  TGraf = class
    G: array [1..N] of TVrchol;
    procedure Dosirky(V: Integer);
  end;

• pre daný graf metóda Dosirky spustí algoritmus do šírky a očísluje všetky vrcholy (do premennej Meno) tak, že štartový vrchol V má Meno = 0, jeho bezprostrední susedia majú postupne hodnoty od 1 vyššie, všetci ich ďalší susedia majú vyššie a vyššie očíslovanie; zrejme sú vrcholy očíslované rôznymi hodnotami 0 až N-1 (nemáme k dispozícii štruktúru Queue)

Cvičenie

práca s grafom a s textovým (binárnym) súborom

• súbor graf.txt obsahuje popis grafu
  • prečítať a vytvoriť graf (prvé meno v riadku má niektorých svojich kamarátov vymenovaných do konca riadka) = graf je neorientovaný
  • zistiť počet vrcholov, počet komponentov, vrchol s najmenším aj najväčším počtom susedov
  • zistiť, či je graf súvislý (algoritmus do hĺbky)

Domáca úloha

1. do reprezentácie grafu doplnte pole a metódu

type
  TGraf = class
    ...
    Komponent: array of Integer;
    procedure UrobKomponenty;
  end;

• metóda do poľa Komponent pre každý vrchol grafu zapíše číslo komponentu, v ktorom sa tento vrchol nachádza; ak sú dva vrcholy v tom istom komponente, majú v tomto poli rovnaké číslo; ak je graf súvislý, všetky vrcholy majú hodnotu 1