Program Generowania Drzewa Rozpinającego Grafu Wszerz Delphi

[SPEEDY2005]

Witam

 

Czy ktoś mógłby pomóc mi w napisaniu programu który ma generować drzewo rozpinające grafu wszerz. Mile widziana każda pomoc, choć głównie chodzi mi o samą procedurę.

[rezo_]

Przepisz sobie na delphi.

 

Zakladam ze graf masz na macierzy adiacencji.

 

const int maxa=5	/*zalozmy ze maksymalnie 5 wierzcholkowe grafy bedziesz rozpatrywal*/int graf[maxa][maxa]={0,1,0,0,1,   /*przykladowy graf na macierzy adiacencji*/				   1,0,1,1,1,				   0,1,0,1,0,				   0,1,1,0,1,				   1,1,0,1,0};enum kolory {bialy, szary, czarny}; /*do kolorowania wierzchokow*/kolory kolor[maxa]; /*przechowuje kolor danego wierzcholka*/int d[maxa]; /*tablica odleglosci od korzenia Twojego drzewa, np d[1] zawiera w jakiej odleglosci od korzenia jest wierzcholek nr 1*/int par[maxa]; /*tablica rodzica dla kazdego wierzcholka, np par[1] zawiera nr wierzcholka ktory jest rodziciem wierzcholka 1*//*Teraz zdefiniujemy kolejke bo przyda sie do BFS'a, jesli masz mozliwosc uzyj jakiej bibliotecznej.*//*------KOLEJKA---------*/int kolejka[maxa];int last=-1;bool empty(){	if (last>=0)return false;	else return true;}void put(int w){kolejka[++last]=w;}int get(){	if(!empty()){		int tmp=kolejka[0];		for (int i=1; i<=last; i++)kolejka[i-1]=kolejka[i];		last--;		return tmp;	}   else cout<<"KOLEJKA PUSTA";}/*-----KONIEC KOLEJKI------------*//*pora na gwozdz programu czyli algorytm przeszukiwania wszerz czyt. BFS*/void bfs(int tab[][maxa], int n, int s){ /*tab-twoj graf,  n-rzeczwista ilosc wierzcholkow <=maxa, s-wierzcholek ktory bedzie korzeniem*/	for (int i=0; i<n; i++){ // ustawiamy dane startowe		kolor[i]=bialy; 		par[i]=-1;		d[i]=-1;	}	d[s]=0; /*dla korzenia ustawiamy odleglosc od korzenia na 0, logiczne nie?*/	kolor[s]=szary;	put(s); /*odkladamy go do kolejki, dalej szuru buru troche i po krzyku, nie bede sie rozpisywal*/	while (!empty()){		int u=get();		for (int i=0; i<n; i++){			if (tab[u][i]){				if (kolor[i]==bialy){					kolor[i]=szary;					par[i]=u;					d[i]=d[u]+1;					put(i);				}			}		}		kolor[u]=czarny;	}}

Po uzyciu funkcji BFS korzeniem Twojego drzewa jest wierzcholek przekazany w parametrze funkcji s. Jak chcesz wiedziec jaka jest odleglosc od korzenia dla jakiegos wierzcholke to uzywasz d[nr_wierzcholka], jak chcesz odtworzyc droge od danego wierzcholka do korzenia to musisz skorzystac z utworzonej tablicy rodzicow 'par' , np tworzac funkcje rekurencyjna path:

 

void path(int s, int v){	if (v==s) cout<<s;	else if (par[v]==-1) cout<<"Droga nie istnieje";	else {		path(s, par[v]);		cout<<" -> "<<v;	}};

Implementowalem pod natchnieniem Wprowadzenia do Algorytmow Cormena. Jak nie czaisz bazy to odsylam tam.

Edytowane 9 Stycznia 2009 przez krawetko

[SPEEDY2005]

Dzięki Ci dobry człowieku:D Jesteś moim mistrzem :rolleyes: