Algorytm DFS i BFS - implementacja

0

Witam, potrzebuje zrobic program ktrory rysuje graf, a następnie przeszukuje go używając algorytmów DFS i BFS. Problem w tym, że nie wiem jak się do tego zabrać :/

Zrobiłem już wczytywanie macierzy z pliku. Format zapisu danych :
3 ; liczba wierzcholkow
011
010
000 ; rozkład krawędzi, od którego wierzchołka do którego

Teraz kod który realizuje rysowanie grafu w kole:

Rekord :

type Tdane = record
 nr : integer;
 x  : currency;
 y : currency;
 odwiedzony :boolean;
end;

Procedura rysująca wierzchołki

procedure TForm1.DrawWierzcholek(ilosc: integer);
 var i : integer;
  x,y : double;
begin
 Memo1.Lines.Clear;
 for i:=1 to ilosc do
  begin
   x := sin(2*Pi*i/ilosc)*100+200;
   y := cos(2*Pi*i/ilosc)*100+200;
    Rec[i].nr := i;
    Rec[i].x := x;
    Rec[i].y := y;
    Rec[i].odwiedzony := false;

   Canvas.Ellipse(Round(x)+20,Round(y)+20,Round(x)-20,Round(y)-20);
   Canvas.TextOut(Round(x)-30,Round(y)-30,IntToStr(i));

  end;

end;

Procedura wczytująca z pliku :

 var f : TStringList;
 x,i,k,w : integer; // w- l. wezlow; x = nr wiersza; k = nr kolumny
 s : string; // zmienna pomocnicza
begin
 F := TStringList.Create;
 F.LoadFromFile('dane.txt');
  w := StrToInt(F.Strings[0]);
 Memo1.Lines.Add('Liczba wezlow : '+inttostr(w));

 SetLength(Rec,w+1);  // REC - jest tablicą dynamiczną

 DrawWierzcholek(w);

 for i := 1 to F.Count-1 do
  begin
    for k := 1 to Length(F.Strings[i]) do
       begin
        if StrToInt(F.Strings[i][k])<> 0 then DrawLinie(i,k);
       end;
  end;

Procedura rysująca linie od jednego do drugiego wierzchołka

procedure TForm1.DrawLinie(a,b : integer);
begin
 Canvas.Pen.Width := 1;
 Canvas.Pen.Color := clBlack;
 Canvas.MoveTo(Round(Rec[a].x),Round(Rec[a].y));

 Canvas.LineTo(Round(Rec[b].x),Round(Rec[b].y));
 Canvas.Pen.Width := 5;
 Canvas.Pen.Color := clRed;

 Canvas.MoveTo(Round(Round(Rec[a].x+Rec[b].x)/2),Round(Round(Rec[a].y+Rec[b].y)/2));
 Canvas.LineTo(Round(Rec[b].x),Round(Rec[b].y));
end;

I teraz pytanie, jak przeszukać graf algorytmami DFS i BFS ? Czy dobrze się do tego zabrałem ? Czy może powinienem jakoś zmienić kod ?

Bardzo prosze o pomoc, bo robie to juz 2-gi dzień i stanołem w miejscu :/ i nie wiem co zrobić. Szukałem po necie informacji na ten temat, nie mniej jednak 90% jest w C/C++ którego nie znam. Tak czy siak nie potrafię zaimplementować tego algorytmu :/

Będę wdzięczny za pomoc, i baaadzo wdzięczny za jakiś kod.

0

Nie umiem Pascala, ale wiem, że BFS wymaga, aby zapisać wszystko na listach sąsiedztwa a nie macierzach :/

1 użytkowników online, w tym zalogowanych: 0, gości: 1