Warszawa, 25 sty 08

siema, tu Julex

Grupa 3T1

Laboratorium Algorytmów i Struktur Danych

Badanie algorytmów grafowych

Cel zadania:

Zbadaj złożoność oczekiwaną algorytmu bfs_tss w funkcji liczby wierzchołków n=2:20. Jako operacje dominujące przyjmij porównanie i podstawienie atrybutu color.

Na tym samym wykresie przedstaw złożonosć dla grafu pełnego.

Omówienie algorytmu:

Przeszukiwanie wszerz (ang. Breadth-first search, w skrócie BFS) to algorytm przeszukiwania grafu używany do przechodzenia lub przeszukiwania drzewa lub grafu. Algorytm zaczyna od korzenia i odwiedza wszystkie połączone z nim węzły. Następnie odwiedza węzły połączone z tymi węzłami i tak dalej, aż do odnalezienia celu.

Przygotowanie:

Przygotowano algorytmy graphgen, bfs_tss, startqueue, enqueue, dequeue. Sprawdzono poprawność działania.

Algorytmy działają poprawnie.

Sposób wykonania zadania:

W algortymie bfs_tss wstawiono licznik zliczający liczbę porównań i podstawień atrybutu color. Licznik jest zwracany jako trzeci atrybut.

Zakodowano program testujący znajdujący się w pliku test.m.

W celu uwzględnienia współczynnika gęstości = 0,25 funkcja graphgen otrzymuje jako drugi argument (liczbę krawędzi) liczbę wyrażającą się wzorem m=((n-1)*n)/8, gdzie n zmienia się od 2 do 20.

Współczynnik directed ustawiono na 0 dla grafu nieskierowanego.

Randset za każdym razem generuje graf pseudulosowy.

Złozoność obliczeniowa oczekiwana wyznaczana jest na podstawie badania 100 próbek.

W tej samej pętli uwzględniono obliczanie złożoności oczekiwanej dla grafu pełnego. Jedyną różnicą jest sposób opisu liczby krawędzi: m=((n-1)*n)/2.

Wyniki:

Czerwony wykres przedstawia wyniki otrzymane dla grafu pełnego, zielony dla grafu o gęstości = 0.25.

Omówienie wyników:

Ponieważ w najgorszym przypadku przeszukiwanie wszerz musi przebyć wszystkie krawędzie prowadzące do wszystkich węzłów, złożoność przeszukiwania wszerz wynosi O(|V| + |E|), gdzie |V| to liczba wierzchołków, a |E| to liczba krawędzi w grafie.

Otrzymane wyniki zgadzają się z teorią.

BFS bada każdy wierzchołek (czyli analizuje jego następników) co najwyżej raz. Badanie wierzchołka polega na analizie wszystkich jego następników (sprawdza czy już w nich byliśmy), a następników ma tyle ile jest krawędzi wychodzących z niego. Z tego wynika, że cały algorytm przeszukuje wszystkie krawędzie (chyba, że do którejś nie jest w stanie dojść).

Powinniśmy więc otrzymać charakterystyki liniowe, wyrażające się sumą liczby krawędzi i wierzchołków.

Zaiste, dla grafu pełnego otrzymaliśmy funkcję liniową, podobnie jak i dla grafu o czterokrotnie mniejszej gęstości.

Mniejsza gęstość (dla każdej liczby wierzchołków mniejsza liczba krawędzi niż w grafie pełnym) implikuje mniejszy współczynnik nachylenia prostej wyrażającej złożoność oczekiwaną obliczeniową algorytmu.

clear;

for n=2:20

x(n)=0;

y(n)=0;

for j=1:100

m=((n-1)*n)/8;

[adj,t_adj]=graphgen(n,m,0,j);

[distance,predecessor,l]=bfs_tss(adj,1,n);

x(n)=x(n)+l;

m=((n-1)*n)/2;

[adj,t_adj]=graphgen(n,m,0,j);

[distance,predecessor,l]=bfs_tss(adj,1,n);

y(n)=y(n)+l;

end

x(n)=x(n)/100;

y(n)=y(n)/100;

end

N=1:20;

% Wykresy

figure(1);

hold off;

plot(N,x,'g-',N,y,'r*');

xlabel('Liczba wierzcholkow'); ylabel('Liczba oper. domin.');

title('Zlozonosc oczekiwana bfs tss');

legend('Wspolczynnik gestosci = 0.25', 'Graf pelny');

grid on;

function [distance,predecessor,l]=bfs_tss(adj,s,len)

% inicjalizacja

l=0;

[Q,head,tail]=startqueue(len);

for i=1:length(adj) color(i)=0; l=l+1; distance(i)=Inf; predecessor(i)=0; end

% zaznaczenie wezla zrodlowego

l=l+1;

color(s)=1; distance(s)=0; predecessor(s)=0;

[Q,tail,err]=enqueue(Q,s,head,tail,len);

l=l+1;%porownanie w enqueue

if (err==1) l=l+1; return; end

l=l+1;

% pobieranie z kolejki dopóki nie jest pusta

while (head~=tail)

l=l+2;%porownanie w dequeue

[u,head,err]=dequeue(Q,head,tail,len);

end

l=l+1;

if (err==1) l=l+1; return; end

l=l+1;

% wprowadzanie do kolejki nowych wierzchołków szarych

for j=1:size(adj(u).sasiedzi,2)

v=adj(u).sasiedzi(j);

if (color(v)==0)

l=l+3;%porownanie w enqueue

color(v)=1; distance(v)=distance(u)+1; predecessor(v)=u;

[Q,tail,err]=enqueue(Q,v,head,tail,len);

if (err==1) l=l+1; return; end

end

end

color(u)=2;

l=l+1;

end

---