Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Cautare latime
- void afisareCoadaOrase(int nrNoduri, int noduri[], char *nume[20]){
- for (int i = 0; i < nrNoduri; i++)
- cout << nume[noduri[i]] << " ";///i=0, noduri[0]=0, nume[noduri[i]]=0 arad;
- cout << endl;
- }
- int latime(int start, int stop, int A[20][20], char *nume[20]) {
- int contorViz = 0;
- int noduri[20];///orasele in asteptare, e o coada
- int nrNoduri = 0; ///nr de noduri din coada
- int viz[20];///viz[i] =1 daca orasul a fost vizitat , 0 altfel.
- int parinte[20];///parinte[i]=j =>j este parintele lui i
- int gasit = 0;
- //initial toate orasele sunt nevizitate
- for (int i = 0; i < 20; i++)
- viz[i] = 0;
- ///Pornim de la nodul de start si il marcam ca vizitat
- viz[start] = 1;
- //pun in coada nodul de start
- noduri[0] = start;
- nrNoduri++;
- cout<<"nrNoduri la pasul 0: "<<nrNoduri<<" "<<endl;
- int contorpas = 0;
- cout << "Pasul " << contorpas << ": ";
- contorpas++;
- afisareCoadaOrase(nrNoduri, noduri, nume);
- while (gasit == 0 && nrNoduri > 0) {
- ///scot nodul din fata - start
- int nod = noduri[0];///am inceput folosirea variabilei nod
- //cout << nume[nod] << " ";
- for (int i = 0; i < nrNoduri - 1; i++)
- noduri[i] = noduri[i + 1];///scoate nod din fata si scade nr de noduri
- nrNoduri--;
- ///scot nodul din fata - end
- //cout<<"nrNoduri dupa for: "<<nrNoduri<<" "<<endl;
- cout<<endl;
- if (nod == stop)
- gasit = 1;
- else
- ///caut in matricea A pe liniea corespunzatoare lui nod vecini adica elementele diferite de 0.
- ///Iau doar
- for (int i = 0; i<20; i++)
- if ((A[nod][i] != 0) && (viz[i] == 0)) {
- noduri[nrNoduri++] = i;// am gasit un vecin nevizitat si il adaug in coada
- viz[i] = 1;//cout << "-" << nume[i] << " aflat la " << A[n][i] << " km distanta" << endl;
- parinte[i] = nod; /// parinte de i retine nodul de unde a plecat
- }
- cout << "Pasul " << contorpas++ << ": ";
- afisareCoadaOrase(nrNoduri, noduri, nume);
- }
- cout << endl;
- int temp = stop;
- int contorTraseu = 0;
- int traseu[20];
- while (parinte[temp] != start) {
- traseu[contorTraseu] = temp;
- contorTraseu++;
- temp = parinte[temp];
- }
- traseu[contorTraseu] = temp;
- contorTraseu++;
- traseu[contorTraseu] = parinte[temp];
- contorTraseu++;
- cout <<"Traseu: ";
- for (int i = contorTraseu - 1; i >= 0; i--) {
- cout <<nume[traseu[i]] << ", ";
- }
- return 0;
- }
- int H[20];
- int CreareMatrice(int A[20][20]) {
- A[0][1] = 75;
- A[1][0] = 75;
- A[0][2] = 140;
- A[2][0] = 140;
- A[0][3] = 118;
- A[3][0] = 118;
- A[1][4] = 71;
- A[4][1] = 71;
- A[4][2] = 151;
- A[2][4] = 151;
- A[3][7] = 111;
- A[7][3] = 111;
- A[7][10] = 70;
- A[10][7] = 70;
- A[10][11] = 75;
- A[11][10] = 75;
- A[11][12] = 120;
- A[12][11] = 120;
- A[2][5] = 99;
- A[5][2] = 99;
- A[2][6] = 80;
- A[6][2] = 80;
- A[6][12] = 146;
- A[12][6] = 146;
- A[6][9] = 97;
- A[9][6] = 97;
- A[12][9] = 138;
- A[9][12] = 138;
- A[5][8] = 211;
- A[8][5] = 211;
- A[9][8] = 101;
- A[8][9] = 101;
- A[8][13] = 90;
- A[13][8] = 90;
- A[8][14] = 85;
- A[14][8] = 85;
- A[14][15] = 98;
- A[15][14] = 98;
- A[15][16] = 86;
- A[16][15] = 86;
- A[14][17] = 142;
- A[17][14] = 142;
- A[17][18] = 92;
- A[18][17] = 92;
- A[18][19] = 87;
- A[19][18] = 87;
- return 0;
- }
- int main() {
- char *nume[20] = { "Arad", "Zerind", "Sibiu", "Timisoara", "Oradea", "Fagaras", "Ramnicu Valcea", "Lugoj", "Bucuresti", "Pitesti", "Mehadia", "Drobeta", "Craiova", "Giurgiu", "Urziceni", "Hirsova", "Eforie", "Vaslui", "Iasi", "Neamt" };
- // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
- for(int i=0; i<20; i++)}
- for(j=0; j<20; j++){
- A[i][j]=0;
- }
- }
- CreareMatrice(A);
- for(int i=0;i<20;i++){
- for(int j=i+1;j<20;j++){
- if(A[i][j]!=0){
- printf("%5d%5d%5d\n",i,j,A[i][j]);
- }
- }
- }
- cout<<"-----------"<<endl;
- CreareVector(H);
- int start = 0, stop = 8;
- cout << endl<<"Cautare in latime:" << endl;
- latime(start, stop, A, nume);
- _getch();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement