Metode de Reprezentare a Grafurilor: Matricea Costurilor 29
1. Ce este Matricea Costurilor?
Matricea costurilor este o metodă de reprezentare a unui graf ponderat (orientat sau neorientat) în care fiecare element din matrice reprezintă costul asociat unei muchii sau unui arc dintre două noduri. Dacă nu există o muchie/arc între două noduri, se utilizează o valoare convențională (de obicei infinit ∞\infty∞).
2. Structura Matricei Costurilor
- Dimensiune:
Matricea este de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde ∣V∣|V|∣V∣ este numărul de noduri. - Elementele matricei:
- C[i][j]=wC[i][j] = wC[i][j]=w, unde www este costul (greutatea) muchiei/arcului (i,j)(i, j)(i,j).
- C[i][j]=∞C[i][j] = \inftyC[i][j]=∞ dacă nu există muchie/arc între iii și jjj.
- Proprietăți:
- Pentru grafuri neorientate: Matricea este simetrică (C[i][j]=C[j][i]C[i][j] = C[j][i]C[i][j]=C[j][i]).
- Pentru grafuri orientate: Matricea poate fi asimetrică (C[i][j]≠C[j][i]C[i][j] \neq C[j][i]C[i][j]=C[j][i]).
- Pentru muchiile/arcele fără cost, se poate utiliza C[i][j]=1C[i][j] = 1C[i][j]=1.
3. Exemple de Grafuri și Matricea Costurilor
Graf Neorientat
Graful:
1–2 (5)
| |
(3) (2)
| |
3–4 (4)
Matricea costurilor:
1 2 3 4
1 0 5 3 ∞
2 5 0 ∞ 2
3 3 ∞ 0 4
4 ∞ 2 4 0
Graf Orientat
Graful:
(1) → (2, 5)
↑ ↓
(4, 7) ← (3, 2)
Matricea costurilor:
1 2 3 4
1 0 5 ∞ ∞
2 ∞ 0 2 ∞
3 ∞ ∞ 0 7
4 7 ∞ ∞ 0
Graf Complet
Un graf complet cu 3 noduri, unde costurile sunt definite:
1–2 (4)
\ /
(3)
Matricea costurilor:
1 2 3
1 0 4 3
2 4 0 3
3 3 3 0
4. Avantaje și Dezavantaje
Avantaje | Dezavantaje |
Simplu de utilizat pentru calcularea drumurilor minime. | Ineficient pentru grafuri sparse (( O( |
Acces direct la costul unei muchii (O(1)O(1)O(1)). | Necesită o convenție pentru muchiile inexistente (∞\infty∞). |
Reprezentare compactă pentru grafuri dense. | Crește consumul de memorie pentru grafuri mari. |
5. Implementare în C++
1. Matricea costurilor pentru graf neorientat
#include <iostream>
#include <vector>
#define INF 100000 // Valoare convențională pentru infinit
using namespace std;
void afisareMatrice(int n, int matrice[100][100]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrice[i][j] == INF)
cout << „INF „;
else
cout << matrice[i][j] << ” „;
}
cout << endl;
}
}
int main() {
int n = 4; // Numărul de noduri
int matrice[100][100];
// Inițializare matrice cu INF
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrice[i][j] = (i == j) ? 0 : INF; // Cost 0 pe diagonală
}
}
// Adăugare muchii cu costuri
matrice[0][1] = matrice[1][0] = 5; // Muchie 1-2, cost 5
matrice[0][2] = matrice[2][0] = 3; // Muchie 1-3, cost 3
matrice[1][3] = matrice[3][1] = 2; // Muchie 2-4, cost 2
matrice[2][3] = matrice[3][2] = 4; // Muchie 3-4, cost 4
cout << „Matricea costurilor pentru graful neorientat:\n”;
afisareMatrice(n, matrice);
return 0;
}
2. Matricea costurilor pentru graf orientat
#include <iostream>
#include <vector>
#define INF 100000 // Valoare convențională pentru infinit
using namespace std;
void afisareMatrice(int n, int matrice[100][100]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrice[i][j] == INF)
cout << „INF „;
else
cout << matrice[i][j] << ” „;
}
cout << endl;
}
}
int main() {
int n = 4; // Numărul de noduri
int matrice[100][100];
// Inițializare matrice cu INF
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrice[i][j] = (i == j) ? 0 : INF; // Cost 0 pe diagonală
}
}
// Adăugare arce cu costuri
matrice[0][1] = 5; // Arc 1 → 2, cost 5
matrice[1][2] = 2; // Arc 2 → 3, cost 2
matrice[3][0] = 7; // Arc 4 → 1, cost 7
matrice[2][3] = 7; // Arc 3 → 4, cost 7
cout << „Matricea costurilor pentru graful orientat:\n”;
afisareMatrice(n, matrice);
return 0;
}
6. Aplicații ale Matricei Costurilor
- Algoritmul Dijkstra:
Utilizat pentru determinarea drumurilor minime într-un graf ponderat. - Algoritmul Floyd-Warshall:
Folosit pentru a calcula toate drumurile minime între perechi de noduri. - Probleme de optimizare:
Matricea costurilor este utilizată pentru problemele de comis-voiajor (TSP) sau alte probleme similare.
7. Concluzie
- Matricea costurilor este o metodă ideală pentru grafuri dense și pentru rezolvarea problemelor de drumuri minime.
- Este mai puțin eficientă pentru grafuri sparse, unde lista de adiacență este mai potrivită.
- Alegerea metodei depinde de aplicație, dimensiunea grafului și densitatea acestuia.