Ajutoooooooooooooor in c++ cu explicatie programului
Se dă un graf orientat cu n noduri și un nod p. Să se afișeze toate nodurile q ale grafului, diferite de p, cu proprietatea că există cel puțin un drum de la p la q și lungimea drumului minim este pară.
Răspunsuri la întrebare
Explicatie :
- Folosim parcurgerea in latime (BFS) a nodurilor unui graf.
- Pornind de la nodul p calculam distanta drumului pana la toate nodurile adiacente. Apoi repetam procedeul pentru fiecare nod adiacent.
- Ordinea in care parcurgem graful este importanta. Trebuie sa ne asiguram ca parcurgem in fiecare moment nodurile cele mai apropiate de nodul p. Pentru acest motiv folosim o coada.
- Am ales sa citesc matricea de adiacenta din fisier pentru a nu fi nevoie sa o introduc mereu de la tastatura.
Program C++ :
#include <iostream>
#include <fstream>
#define NMAX 10
using namespace std;
//Citesc matricea declarata static din fisierul date.txt
void citesc(bool matrice[10][10], int& nr_noduri) {
ifstream file("date.txt");
if (!file.is_open()) return;
file >> nr_noduri;
for (int linie = 1; linie <= nr_noduri; linie++) {
for (int coloana = 1; coloana <= nr_noduri; coloana++) {
file >> matrice[linie][coloana];
}
}
file.close();
}
void drum_minim_bfs(bool mat[NMAX][NMAX], int nr_noduri, int nod_sursa, int lungime_drum[]) {
//Implementeaza coada
int index_cap = 0;
int index_coada = 0;
int coada[NMAX] = { 0 };
//Adauga nodul p in coada
coada[index_coada++] = nod_sursa;
//Cat timp coada nu este goala
while (index_cap != index_coada) {
//Parcurge fiecare nod adiacent cu nodul din capul cozii.
for (int nod = 1; nod <= nr_noduri; nod++) {
if (mat[nod][coada[index_cap]]) {
//Daca nodul nu a fost vizitat
if (!lungime_drum[nod]) {
//Calculeaza lungimea drumului din p in nod
lungime_drum[nod] = lungime_drum[coada[index_cap]] + 1;
//Adauga nodul la finalul cozii pentru ca nodurile adiacente cu acesta sa fie procesate
coada[index_coada++] = nod;
}
}
}
//Sterge nodul procesat din coada
index_cap++;
}
}
int main() {
bool mat[NMAX][NMAX]; //Matrice adiacenta graf
int n; //Numar noduri
//Citesc matrice adiacenta
citesc(mat, n);
//Primeste id nod sursa
int p;
cout << "Nodul de la care se incepe cautarea : ";
cin >> p;
//Vector care retine lungimea drumului de la nodul sursa la celelalte noduri
int lungime_drum[NMAX] = {0};
drum_minim_bfs(mat, n, p, lungime_drum);
lungime_drum[p] = 0;
//Afiseaza totate nodurile pentru care exista un drum de la p minim par
cout << "\nNoduri cu drum minim par : ";
for (int q = 0; q <= n; q++) {
if (lungime_drum[q] && lungime_drum[q] % 2 == 0)
cout << q << " ";
}
}
