ASD 31.V.2012ASD 31.V.2012, Laborki, ASD
[ Pobierz całość w formacie PDF ]
1. Zaproponuj odpowiednie struktury danych do implementacji algorytmu przeszukiwania grafu wszerz (BFS). Nastepnie zaimplementuj algorytm BSF.#include <cstdlib>#include <iostream>#define NMAX 6#define N 1000using namespace std;void print(int t[], int n);int main(int argc, char *argv[]){ int u,i=0,last=0;;int Adj[NMAX][NMAX] = {{0,1,1,0,0,0},{1,0,0,1,0,0},{1,0,0,1,1,0},{0,1,1,0,0,1},{0,0,1,0,0,1},{0,0,0,1,1,0},};int list[NMAX] = {N,N,N,N,N,N};int dist[NMAX] = {N,N,N,N,N,N};int col[NMAX] = {0};cout << "Podaj wierzcholek ktory bedzie zrodlem";cin >> u;list[0] = u;dist[0] = 0;col[u] = 1;while (i<= last){for (int j=0;j<=NMAX;j++){if(Adj[j][list[i]] & col[j]==0){last++;list[last]=j;dist[last]=dist[i]+1;col[j]=1;}}i++;}cout << " Lista list wyglada nastepujaco";print(list, NMAX);cout << " Lista dist wyglada nastepujaco";print(dist, NMAX);cout << " Lista col wyglada nastepujaco";print(col, NMAX);system("PAUSE");return EXIT_SUCCESS;}void print(int t[], int n){cout << endl << endl;for(int i=0; i<n; i++)cout << i << "-ty element jest rowny " << t[i] << endl;cout << endl << endl;}5. Zaproponuj struktury danych i zaimplementuj algorytm Prima znajdowania minimalnego drzewa rozpinajacego.#include <cstdlib>#include <iostream>#define NMAX 6#define N 1000using namespace std;void print(int t[], int n);int main(int argc, char *argv[]){int u, tmp, tmp1;int Adj[NMAX][NMAX] = {{0,3,2,0,0,0},{3,0,0,1,0,0},{2,0,0,2,1,0},{0,1,2,0,0,1},{0,0,1,0,0,3},{0,0,0,1,3,0},};int dist[NMAX] = {N,N,N,N,N,N};int col[NMAX] = {0};cout<<"Podaj wierzcholek ktory bedzie zrodlem ";cin>>u;dist[u]=0;for(int k=0; k<NMAX; k++){tmp1=NMAX;for(int l=0; l<NMAX; l++)if(col[l]==0 && dist[l]<tmp1) {tmp=l; tmp1 = dist[l];}for(int l=0; l<NMAX; l++)if(Adj[tmp][l]!=0 && Adj[tmp][l] < dist[l] && col[l]==0)dist[l]=Adj[tmp][l];col[tmp]=1;}cout << " Lista dist wyglada nastepujaco ";print(dist, NMAX);cout << " Lista col wyglada nastepujaco ";print(col, NMAX);system("PAUSE");return EXIT_SUCCESS;}void print(int t[], int n){cout << endl << endl;for(int i=0; i<n; i++)cout << i << "-ty element jest rowny " << t[i] << endl;cout << endl << endl;} [ Pobierz całość w formacie PDF ] |
Podobne
|