|
|
| Riadok 1: |
Riadok 1: |
| | {{Nadpis| 34. Cvičenie}} | | {{Nadpis| 34. Cvičenie}} |
| | [[34.Prednaska|< 34.Prednáška]] | [[34.Prednaska/Ulohy|riešené úlohy]] | | [[34.Prednaska|< 34.Prednáška]] | [[34.Prednaska/Ulohy|riešené úlohy]] |
| − |
| |
| − |
| |
| | | | |
| | <!-- --> | | <!-- --> |
| Riadok 22: |
Riadok 20: |
| | |} | | |} |
| | * 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''') | | * 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 [[Media:P34_graf.txt|graf.txt]] obsahuje popis grafu
| |
| − | ** prečítať a vytvoriť graf (prvé meno v každom riadku má uvedených niektorých svojich kamarátov postupne vymenovaných do konca riadka) = graf je neorientovaný
| |
| − | ** spracovať do matice susedností (zdá sa, že vrcholov je menej ako 1000)
| |
| − | type TGraf = class
| |
| − | Pole: array of array of Boolean;
| |
| − | Meno: array of string;
| |
| − | constructor Create;
| |
| − | function OpakujeSa(S: string): Boolean;
| |
| − | end;
| |
| − |
| |
| − | * najprv v konštruktore prečítame všetky mená a zaradíme ich do poľa '''Mena''' - každé meno práve raz:
| |
| − | constructor TGraf.Create;
| |
| − | var
| |
| − | F: TextFile;
| |
| − | S, T: string;
| |
| − | I, J: Integer;
| |
| − | begin
| |
| − | AssignFile(F, 'graf.txt');
| |
| − | Reset(F);
| |
| − | while not EOF(F) do
| |
| − | begin
| |
| − | ReadLn(F, S);
| |
| − | while S <> {{''}} do begin
| |
| − | P := Pos(' ', S + ' ');
| |
| − | T := Copy(S, 1, P - 1);
| |
| − | if not OpakujeSa(T) do
| |
| − | begin
| |
| − | SetLength(Meno, Length(Meno) + 1);
| |
| − | Meno[High(Meno)] := T;
| |
| − | end;
| |
| − | Delete(S, 1, P);
| |
| − | end;
| |
| − | end;
| |
| − | // Tu bude kod na zostrojenie grafu
| |
| − | end;
| |
| − | * test, aby sa slová v poli '''Mena''' neopakovali
| |
| − | function TGraf.OpakujeSa(S: string): Boolean;
| |
| − | var
| |
| − | I: Integer;
| |
| − | begin
| |
| − | Result := True;
| |
| − | for I := 0 to High(Meno) do
| |
| − | if Meno[I] = S then
| |
| − | Exit;
| |
| − | Result := False;
| |
| − | end;
| |
| − | * v hlavnom programe môžeme otestovať a odladiť
| |
| − | ...
| |
| − | Graf := TGraf.Create;
| |
| − | for I := 0 to High(Graf.Meno) do
| |
| − | Write(Graf.Meno[I], ' ');
| |
| − | Writeln(Length(Graf.Meno));
| |
| − | ...
| |
| − | * funkcia, ktorá zistí index mena v poli '''Mena'''
| |
| − | :* funkciu '''OpakujeSa''' teraz už nebudeme potrebovať
| |
| − | function Index(S: string): Integer;
| |
| − | var
| |
| − | I: Integer;
| |
| − | begin
| |
| − | for I := 0 to High(Memo) do
| |
| − | if Memo[I] = S then
| |
| − | begin
| |
| − | Result := I;
| |
| − | Exit;
| |
| − | end;
| |
| − | Result := -1;
| |
| − | end;
| |
| − | * dopíšeme zostrojenie grafu v konštruktore '''TGraf''':
| |
| − | SetLength(Pole, Length(Meno), Length(Meno)); ''// najprv inicializujeme dvojrozmerné pole''
| |
| − | for I := 0 to High(Pole) do
| |
| − | for J := 0 to High(Pole) do
| |
| − | Pole[I, J] := False;
| |
| − | Reset(F);
| |
| − | while not EOF(F) do
| |
| − | begin
| |
| − | ReadLn(F, S);
| |
| − | P:=Pos(' ', S + ' ');
| |
| − | I := Index(Copy(S, 1, P - 1));
| |
| − | Delete(S, 1, P);
| |
| − | while S <> {{''}} do
| |
| − | begin
| |
| − | P:=Pos(' ', S + ' ');
| |
| − | J := Index(Copy(S, 1, P - 1)); ''// index ďalšieho mena v riadku''
| |
| − | Pole[I, J] := True;
| |
| − | Pole[J, I] := True;
| |
| − | Delete(S, 1, P);
| |
| − | end;
| |
| − | end;
| |
| − | * aby sme mohli vypísať vrchol s najmenším a tiež najväčším počtom susedov
| |
| − | function TGraf.PocetSusedov(K: Integer): Integer;
| |
| − | var
| |
| − | I:Integer;
| |
| − | begin
| |
| − | Result := 0;
| |
| − | for I := 0 to High(Pole) do
| |
| − | if Pole[K, I] then begin
| |
| − | Inc(Result);
| |
| − | end;
| |
| − | * aby sme mohli zistiť, či je graf súvislý
| |
| − | procedure TGraf.DoHlbky(V: Integer);
| |
| − | var
| |
| − | I: Integer;
| |
| − | begin
| |
| − | Visited[V] := True;
| |
| − | for I:= 0 to High(Pole) do
| |
| − | if Pole[I][V] and not Visited[I] then
| |
| − | DoHlbky(I);
| |
| − | end;
| |
| − |
| |
| − | function TGraf.JeSuvisly : Boolean;
| |
| − | var
| |
| − | I: Integer;
| |
| − | begin
| |
| − | SetLength(Visited, Length(Pole));
| |
| − | for I := 0 to High(Pole) do
| |
| − | Visited[I] := False;
| |
| − | DoHlbky(0);
| |
| − | for I := 0 to High(Pole) do
| |
| − | if Visited[I] = False then
| |
| − | Exit(False); ''// takto Exit ešte nastaví aj Result''
| |
| − | Result := True;
| |
| − | end;
| |
| − |
| |
| − |
| |
| − | <!-- -->
| |
| − |
| |
| − | === Domáca úloha ===
| |
| − |
| |
| − | 1. do reprezentácie grafu doplnte pole a metódu
| |
| − | {{Prog}}
| |
| − | 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
| |
1. graf je zadeklarovaný:
