34.Prednaska/Cvicenie0

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 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;

• 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

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