|
|
| (3 intermediate revisions by the same user not shown) |
| 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;
| |
| − |
| |
| − | * konštruktor
| |
| − | 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 opakovania
| |
| − | function opakujesa(S:String) : boolean;
| |
| − | var
| |
| − | I: Integer;
| |
| − | begin
| |
| − | Result := True;
| |
| − | for I := 0 to High(Memo) do
| |
| − | if Memo[I] = S then
| |
| − | Exit;
| |
| − | Result := False;
| |
| − | end;
| |
| − | * 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
| |
| − | :* funkciu '''opakujesa''' nam vlastne netreba
| |
| − | function index(S:String) : integer;
| |
| − | var
| |
| − | I: Integer;
| |
| − | begin
| |
| − | Result := -1;
| |
| − | for I := 0 to High(Memo) do
| |
| − | if Memo[I] = S then
| |
| − | Result := I;
| |
| − | end;
| |
| − | * zostrojenie grafu
| |
| − | SetLength(Pole, Length(Meno), Length(Meno));
| |
| − | for I := 0 to High(Pole) do
| |
| − | for J := 0 to High(Pole) do
| |
| − | Pole[I, J] := False;
| |
| − | //alebo
| |
| − | //FillChar(Pole[0,0], ..., 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));
| |
| − | Pole[I, J] := True;
| |
| − | Pole[J, I] := True;
| |
| − | Delete(S, 1, P);
| |
| − | end;
| |
| − | end;
| |
| − | * vrchol s najmenším a najväčším počtom susedov
| |
| − | function 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;
| |
| − | * zistiť, či je garf súvislý
| |
| − | procedure TGraf.DoHlbky(V: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;
| |
| − | begin
| |
| − | SetLen)gth(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);
| |
| − | 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ý:
