3. Elaborați procedura de determinare a matricei drumurilor într-un graf orientat.
4. Realizaţi un program cu următoarele funcţii:
1) introducerea grafului ca matrice de adiacență (graf orientat) cu posibilităţi de corectare a informaţiei;
2) determinarea matricei drumurilor;
3) extragerea informaţiei la display;
codul 100% functional fara greseli pentru toate problemele rezolvate corect pentru toate cazurile de nota 10 in limbajul C++/C#
Răspunsuri la întrebare
Exercitiile rezolvate:
Ex 3
Procedura arată astfel:
1) Inițializăm matricea drumurilor cu valorile corespunzătoare muchiilor grafului.
2) Pentru fiecare nod i din graf, parcurgem toți vecinii săi j și verificăm dacă există un drum mai scurt de la i la j prin oricare dintre nodurile intermediare. Dacă există un astfel de drum, actualizăm matricea drumurilor.
3) După parcurgerea tuturor nodurilor, matricea drumurilor va conține distanțele minime între oricare două noduri din graf.
Ex 4
#include <iostream>
#include <iomanip>
using namespace std;
// functie pentru citirea matricei de adiacenta de la tastatura
void citireGraf(int **graf, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << "Introduceti valoarea pentru nodul " << i+1 << " si nodul " << j+1 << ": ";
cin >> graf[i][j];
}
}
}
// functie pentru afisarea matricei de adiacenta
void afisareGraf(int **graf, int n) {
cout << "Matricea de adiacenta este: " << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << setw(2) << graf[i][j] << " ";
}
cout << endl;
}
}
// functie pentru calcularea matricei drumurilor
void matriceDrumuri(int **graf, int n) {
int **drumuri = new int*[n];
for (int i = 0; i < n; i++) {
drumuri[i] = new int[n];
for (int j = 0; j < n; j++) {
drumuri[i][j] = graf[i][j];
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (drumuri[i][k] && drumuri[k][j]) {
drumuri[i][j] = 1;
}
}
}
}
cout << "Matricea drumurilor este: " << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << setw(2) << drumuri[i][j] << " ";
}
cout << endl;
}
}
// functie principala
int main() {
int n;
cout << "Introduceti numarul de noduri din graf: ";
cin >> n;
int **graf = new int*[n];
for (int i = 0; i < n; i++) {
graf[i] = new int[n];
}
citireGraf(graf, n);
afisareGraf(graf, n);
matriceDrumuri(graf, n);
return 0;
}
P.S: codul functioneaza, compilat folosind https://www.onlinegdb.com/online_c++_compiler.
***
- sper ca te-am ajutat!
#adrianrtx #homeworkhelp