34.Prednaska/Cvicenie

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

34. Cvičenie


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


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;
  • v hlavnom programe môžeme otestovať a odladiť
...
Graf := TGraf.Create;
for I := 0 to High(Graf.Meno) do
  Write(Graf.Meno[I], ' ');
WriteLn;
Writeln('pocet vrcholov grafu = ', 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;
  • a v hlavnom programe
...
PMax := 0;
PMin := MaxInt;
for I := 0 to High(Graf.Pole) do
begin
  P := Graf.PocetSusedov(I);
  if P > PMax then
  begin
    PMax := P;
    Max := I;
  end;
  if P < PMin then
  begin
    PMin := P;
    Min := I;
  end;
end;
WriteLn('najviac susedov ma ', Graf.Mena[Max], ' s poctom susedov ', PMax);
WriteLn('najmenej susedov ma ', Graf.Mena[Min], ' s poctom susedov ', PMin);
  • 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

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