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.