Metode de Reprezentare a Grafurilor: Matricea de Incidență
1. Ce este Matricea de Incidență?
Matricea de incidență este o metodă de reprezentare a unui graf (neorientat sau orientat) utilizând o matrice III de dimensiune ∣V∣×∣E∣|V| \times |E|∣V∣×∣E∣, unde:
- ∣V∣|V|∣V∣ este numărul de noduri ale grafului.
- ∣E∣|E|∣E∣ este numărul de muchii (sau arce) ale grafului.
2. Definiție
Pentru un graf G=(V,E)G = (V, E)G=(V,E):
- În cazul unui graf neorientat, I[i][j]=1I[i][j] = 1I[i][j]=1 dacă nodul viv_ivi este incident la muchia eje_jej.
- În cazul unui graf orientat:
- I[i][j]=−1I[i][j] = -1I[i][j]=−1 dacă nodul viv_ivi este nodul de origine al arcului eje_jej.
- I[i][j]=1I[i][j] = 1I[i][j]=1 dacă nodul viv_ivi este nodul de destinație al arcului eje_jej.
- I[i][j]=0I[i][j] = 0I[i][j]=0 altfel.
3. Caracteristici
- Grafuri neorientate:
- Matricea conține doar valori binare (0 și 1).
- O muchie este reprezentată de două elemente de valoare 1.
- Grafuri orientate:
- Matricea poate conține valori −1,0-1, 0−1,0 și 111.
- Arcele au direcții bine definite, iar matricea reflectă această orientare.
- Grafuri ponderate:
- Valorile din matrice pot reprezenta greutățile muchiilor în loc de valori binare.
4. Exemplu pentru Grafuri Neorientate
Graf:
1–2
| |
4–3
Reprezentare:
- Noduri: V={1,2,3,4}V = \{1, 2, 3, 4\}V={1,2,3,4}
- Muchii: E={e1={1,2},e2={1,4},e3={2,3},e4={3,4}}E = \{e_1 = \{1, 2\}, e_2 = \{1, 4\}, e_3 = \{2, 3\}, e_4 = \{3, 4\}\}E={e1={1,2},e2={1,4},e3={2,3},e4={3,4}}
Matricea de incidență:
e1 e2 e3 e4
1: 1 1 0 0
2: 1 0 1 0
3: 0 0 1 1
4: 0 1 0 1
5. Exemplu pentru Grafuri Orientate
Graf:
(1) → (2)
↑ ↓
(4) ← (3)
Reprezentare:
- Noduri: V={1,2,3,4}V = \{1, 2, 3, 4\}V={1,2,3,4}
- Arce: E={e1=(1,2),e2=(3,4),e3=(4,1),e4=(2,3)}E = \{e_1 = (1, 2), e_2 = (3, 4), e_3 = (4, 1), e_4 = (2, 3)\}E={e1=(1,2),e2=(3,4),e3=(4,1),e4=(2,3)}
Matricea de incidență:
e1 e2 e3 e4
1: -1 0 1 0
2: 1 0 0 -1
3: 0 -1 0 1
4: 0 1 -1 0
6. Avantaje și Dezavantaje
| Avantaje | Dezavantaje |
| Reprezentare simplă a conexiunilor dintre noduri și muchii. | Necesită spațiu mai mare (( O( |
| Ușor de utilizat pentru calcule matematice și algoritmi. | Ineficient pentru grafuri sparse sau foarte mari. |
| Compatibilitate cu grafuri orientate și ponderate. | Traversarea vecinilor unui nod necesită timp ( O( |
7. Implementare în C++
1. Matricea de incidență pentru graf neorientat
#include <iostream>
using namespace std;
void afisareMatrice(int n, int m, int matrice[100][100]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << matrice[i][j] << ” „;
}
cout << endl;
}
}
int main() {
int n = 4; // Numărul de noduri
int m = 4; // Numărul de muchii
int matrice[100][100] = {0};
// Adăugare muchii
matrice[0][0] = 1; matrice[1][0] = 1; // Muchie e1 = {1, 2}
matrice[0][1] = 1; matrice[3][1] = 1; // Muchie e2 = {1, 4}
matrice[1][2] = 1; matrice[2][2] = 1; // Muchie e3 = {2, 3}
matrice[2][3] = 1; matrice[3][3] = 1; // Muchie e4 = {3, 4}
cout << „Matricea de incidență pentru graful neorientat:\n”;
afisareMatrice(n, m, matrice);
return 0;
}
2. Matricea de incidență pentru graf orientat
#include <iostream>
using namespace std;
void afisareMatrice(int n, int m, int matrice[100][100]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << matrice[i][j] << ” „;
}
cout << endl;
}
}
int main() {
int n = 4; // Numărul de noduri
int m = 4; // Numărul de arce
int matrice[100][100] = {0};
// Adăugare arce
matrice[0][0] = -1; matrice[1][0] = 1; // Arc e1 = (1, 2)
matrice[2][1] = -1; matrice[3][1] = 1; // Arc e2 = (3, 4)
matrice[3][2] = -1; matrice[0][2] = 1; // Arc e3 = (4, 1)
matrice[1][3] = -1; matrice[2][3] = 1; // Arc e4 = (2, 3)
cout << „Matricea de incidență pentru graful orientat:\n”;
afisareMatrice(n, m, matrice);
return 0;
}
8. Aplicații ale Matricei de Incidență
- Analiza conexiunilor nodurilor:
Matricea de incidență facilitează analiza conexiunilor dintre noduri și muchii. - Probleme de flux:
Este utilizată pentru calcularea fluxului maxim în rețele orientate. - Reprezentarea ponderată:
Matricea poate fi extinsă pentru a include greutăți asociate muchiilor/arcelor.
9. Concluzie
- Matricea de incidență este o metodă eficientă de reprezentare pentru grafuri dense sau pentru probleme care implică analiza muchiilor/arcelor.
- Este mai puțin eficientă pentru grafuri sparse sau foarte mari, comparativ cu alte metode (ex.: lista de adiacență).
- Alegerea metodei de reprezentare depinde de tipul de problemă și de proprietățile grafului.
Metode de Reprezentare a Grafurilor: Lista Nodurilor
1. Ce este Lista Nodurilor?
Lista nodurilor este o metodă de reprezentare a grafurilor în care se specifică explicit nodurile grafului, iar conexiunile dintre noduri (muchiile sau arcele) sunt tratate separat.
Aceasta este o metodă simplă și fundamentală, utilizată adesea ca bază pentru alte tipuri de reprezentări, cum ar fi lista de adiacență sau lista muchiilor.
2. Structura Listei Nodurilor
- Noduri: Se reprezintă ca o colecție de elemente distincte (o listă, un vector, un tablou etc.).
- Conexiuni (opțional): Legăturile dintre noduri sunt gestionate separat, utilizând alte structuri de date (ex.: liste de adiacență, matrice de adiacență).
3. Exemple de Grafuri
Graf Neorientat
Graful:
1–2
| |
4–3
Lista nodurilor:
V = {1, 2, 3, 4}
Lista muchiilor:
E = {(1, 2), (1, 4), (2, 3), (3, 4)}
Graf Orientat
Graful:
(1) → (2)
↑ ↓
(4) ← (3)
Lista nodurilor:
V = {1, 2, 3, 4}
Lista arcelor:
E = {(1, 2), (3, 4), (4, 1), (2, 3)}
4. Implementare în C++
1. Reprezentare simplă a nodurilor
#include <iostream>
#include <vector>
using namespace std;
int main() {
// Lista nodurilor
vector<int> noduri = {1, 2, 3, 4};
// Afișare lista nodurilor
cout << „Nodurile grafului sunt: „;
for (int nod : noduri) {
cout << nod << ” „;
}
cout << endl;
return 0;
}
2. Reprezentare a nodurilor și muchiilor
#include <iostream>
#include <vector>
using namespace std;
int main() {
// Lista nodurilor
vector<int> noduri = {1, 2, 3, 4};
// Lista muchiilor
vector<pair<int, int>> muchii = {
{1, 2},
{1, 4},
{2, 3},
{3, 4}
};
// Afișare lista nodurilor
cout << „Nodurile grafului sunt: „;
for (int nod : noduri) {
cout << nod << ” „;
}
cout << endl;
// Afișare lista muchiilor
cout << „Muchiile grafului sunt: „;
for (auto muchie : muchii) {
cout << „(” << muchie.first << „, ” << muchie.second << „) „;
}
cout << endl;
return 0;
}
3. Reprezentare a nodurilor și arcelor (pentru grafuri orientate)
#include <iostream>
#include <vector>
using namespace std;
int main() {
// Lista nodurilor
vector<int> noduri = {1, 2, 3, 4};
// Lista arcelor
vector<pair<int, int>> arce = {
{1, 2},
{3, 4},
{4, 1},
{2, 3}
};
// Afișare lista nodurilor
cout << „Nodurile grafului sunt: „;
for (int nod : noduri) {
cout << nod << ” „;
}
cout << endl;
// Afișare lista arcelor
cout << „Arcele grafului sunt: „;
for (auto arc : arce) {
cout << „(” << arc.first << „, ” << arc.second << „) „;
}
cout << endl;
return 0;
}
5. Avantaje și Dezavantaje
| Avantaje | Dezavantaje |
| Foarte simplă de utilizat pentru grafuri mici. | Nu oferă informații despre conexiuni direct. |
| Ideală ca bază pentru alte reprezentări. | Necesită structuri suplimentare pentru muchii. |
6. Aplicații ale Listei Nodurilor
- Modelarea rețelelor: Lista nodurilor poate reprezenta entitățile (ex.: computere, orașe) dintr-o rețea.
- Graful gol: Reprezentarea unui graf fără conexiuni, utilă pentru inițializări.
- Bază pentru algoritmi: Listele de noduri sunt utilizate în construcția listelor de adiacență sau a altor reprezentări.
7. Concluzie
Lista nodurilor este o metodă fundamentală, folosită pentru a reprezenta structura de bază a unui graf. Deși nu include informații despre conexiuni, este utilă în combinație cu alte metode (lista de adiacență, lista muchiilor) pentru a construi modele mai complexe.
Metode de Reprezentare a Grafurilor: Lista Arcelor
1. Ce este Lista Arcelor?
Lista arcelor este o metodă de reprezentare a unui graf (neorientat sau orientat) printr-o listă de perechi care descriu conexiunile dintre noduri. Această metodă este utilă pentru a stoca și prelucra graful într-un mod eficient, mai ales atunci când graful este sparse (cu puține conexiuni comparativ cu numărul de noduri).
2. Structura Listei Arcelor
- Noduri: Se presupune că nodurile sunt numerotate sau denumite distinct.
- Arce/Muchii: O listă de perechi (u,v)(u, v)(u,v), unde uuu și vvv sunt noduri conectate:
- Pentru grafuri neorientate, (u,v)(u, v)(u,v) și (v,u)(v, u)(v,u) sunt considerate echivalente.
- Pentru grafuri orientate, direcția contează: (u,v)≠(v,u)(u, v) \neq (v, u)(u,v)=(v,u).
- Opțional: Se pot adăuga greutăți pentru muchii/arce, reprezentându-le astfel sub forma (u,v,w)(u, v, w)(u,v,w), unde www este greutatea.
3. Avantaje și Dezavantaje
| Avantaje | Dezavantaje |
| Consum redus de memorie pentru grafuri sparse. | Accesarea vecinilor unui nod necesită parcurgerea întregii liste. |
| Ușor de manipulat și sortat (ex.: pentru algoritmul Kruskal). | Nu este eficient pentru grafuri dense. |
| Ideală pentru grafuri orientate și ponderate. | Traversarea grafului poate fi mai complexă. |
4. Exemplu pentru Grafuri
Graf Neorientat
Graful:
1–2
| |
4–3
Lista arcelor:
E = {(1, 2), (1, 4), (2, 3), (3, 4)}
Graf Orientat
Graful:
(1) → (2)
↑ ↓
(4) ← (3)
Lista arcelor:
E = {(1, 2), (3, 4), (4, 1), (2, 3)}
Graf Ponderat
Graful:
1–2 (5)
| |
(3) (2)
| |
3–4 (4)
Lista arcelor:
E = {(1, 2, 5), (1, 3, 3), (2, 4, 2), (3, 4, 4)}
5. Implementare în C++
1. Reprezentare a arcelor pentru graf neorientat
#include <iostream>
#include <vector>
using namespace std;
int main() {
// Lista arcelor
vector<pair<int, int>> muchii = {
{1, 2},
{1, 4},
{2, 3},
{3, 4}
};
// Afișare lista arcelor
cout << „Muchiile grafului sunt:\n”;
for (auto muchie : muchii) {
cout << „(” << muchie.first << „, ” << muchie.second << „)\n”;
}
return 0;
}
2. Reprezentare a arcelor pentru graf orientat
#include <iostream>
#include <vector>
using namespace std;
int main() {
// Lista arcelor
vector<pair<int, int>> arce = {
{1, 2},
{3, 4},
{4, 1},
{2, 3}
};
// Afișare lista arcelor
cout << „Arcele grafului sunt:\n”;
for (auto arc : arce) {
cout << „(” << arc.first << ” → ” << arc.second << „)\n”;
}
return 0;
}
3. Reprezentare a arcelor pentru graf ponderat
#include <iostream>
#include <vector>
using namespace std;
int main() {
// Lista arcelor ponderate
vector<tuple<int, int, int>> arce = {
{1, 2, 5},
{1, 3, 3},
{2, 4, 2},
{3, 4, 4}
};
// Afișare lista arcelor ponderate
cout << „Arcele grafului ponderat sunt:\n”;
for (auto arc : arce) {
cout << „(” << get<0>(arc) << „, ” << get<1>(arc) << „, ” << get<2>(arc) << „)\n”;
}
return 0;
}
6. Aplicații ale Listei Arcelor
- Algoritmul Kruskal:
Lista arcelor este utilizată pentru a găsi arborele de acoperire minimă prin sortarea arcelor după greutate. - Rețele și grafuri ponderate:
Lista arcelor este esențială pentru problemele de flux sau drumuri minime. - Detectarea ciclurilor:
Prin analizarea conexiunilor dintre noduri, se pot identifica cicluri.
7. Compararea Listei Arcelor cu Alte Metode
| Metodă | Memorie | Complexitate acces vecini | Aplicații tipice |
| Lista Arcelor | ( O( | E | ) ) |
| Matrice de Adiacență | ( O( | V | ^2) ) |
| Lista de Adiacență | ( O( | V | + |
8. Concluzie
- Lista arcelor este o metodă simplă și eficientă pentru reprezentarea grafurilor sparse.
- Este ideală pentru algoritmi care necesită procesarea arcelor individuale (ex.: Kruskal).
- Pentru grafuri dense, alte metode (ex.: matricea de adiacență) sunt mai eficiente.
Metode de Reprezentare a Grafurilor: Matricea Costurilor
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.
Metode de Reprezentare a Grafurilor: Matricea Drumurilor
1. Ce este Matricea Drumurilor?
Matricea drumurilor este o metodă de reprezentare a unui graf care indică existenta unui drum între două noduri. Aceasta este o matrice binară PPP de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde:
- ∣V∣|V|∣V∣ reprezintă numărul de noduri.
- P[i][j]=1P[i][j] = 1P[i][j]=1 dacă există un drum (oricât de lung) între nodurile iii și jjj.
- P[i][j]=0P[i][j] = 0P[i][j]=0 dacă nu există niciun drum între nodurile iii și jjj.
2. Caracteristici
- Grafuri neorientate:
- Matricea este simetrică (P[i][j]=P[j][i]P[i][j] = P[j][i]P[i][j]=P[j][i]).
- Grafuri orientate:
- Matricea nu este neapărat simetrică (P[i][j]≠P[j][i]P[i][j] \neq P[j][i]P[i][j]=P[j][i]).
- Drumuri reflexive:
- Diagonala principală conține P[i][i]=1P[i][i] = 1P[i][i]=1, deoarece orice nod are un drum către el însuși (inclusiv drumuri de lungime zero).
- Calculul matricei drumurilor:
- Matricea drumurilor se poate calcula folosind puterea matricei de adiacență sau algoritmi precum Floyd-Warshall.
3. Exemple de Grafuri și Matricea Drumurilor
Graf Neorientat
Graful:
1–2
| |
4–3
Lista muchiilor:
E = {(1, 2), (1, 4), (2, 3), (3, 4)}
Matricea drumurilor:
1 2 3 4
1 1 1 1 1
2 1 1 1 1
3 1 1 1 1
4 1 1 1 1
Graf Orientat
Graful:
(1) → (2)
↑ ↓
(4) ← (3)
Lista arcelor:
E = {(1, 2), (2, 3), (3, 4), (4, 1)}
Matricea drumurilor:
1 2 3 4
1 1 1 1 1
2 1 1 1 1
3 1 1 1 1
4 1 1 1 1
4. Calculul Matricei Drumurilor
- Folosind matricea de adiacență:
- Dacă AAA este matricea de adiacență, matricea drumurilor PPP se calculează ca: P=A+A2+A3+⋯+A∣V∣P = A + A^2 + A^3 + \dots + A^{|V|}P=A+A2+A3+⋯+A∣V∣
- P[i][j]=1P[i][j] = 1P[i][j]=1 dacă există un drum de orice lungime de la iii la jjj.
- Algoritmul Floyd-Warshall:
- Este un algoritm eficient pentru calcularea matricei drumurilor într-un graf.
5. Implementare în C++
1. Calculul Matricei Drumurilor folosind Matricea de Adiacență
#include <iostream>
#include <vector>
#define INF 100000
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++) {
cout << matrice[i][j] << ” „;
}
cout << endl;
}
}
void calculeazaDrumuri(int n, int adiacenta[100][100], int drumuri[100][100]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
drumuri[i][j] = adiacenta[i][j];
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
drumuri[i][j] = drumuri[i][j] || (drumuri[i][k] && drumuri[k][j]);
}
}
}
}
int main() {
int n = 4; // Numărul de noduri
int adiacenta[100][100] = {
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
int drumuri[100][100] = {0};
calculeazaDrumuri(n, adiacenta, drumuri);
cout << „Matricea drumurilor:\n”;
afisareMatrice(n, drumuri);
return 0;
}
2. Calculul Matricei Drumurilor folosind Floyd-Warshall
#include <iostream>
using namespace std;
void floydWarshall(int n, int matrice[100][100]) {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrice[i][j] = matrice[i][j] || (matrice[i][k] && matrice[k][j]);
}
}
}
}
void afisareMatrice(int n, int matrice[100][100]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << matrice[i][j] << ” „;
}
cout << endl;
}
}
int main() {
int n = 4;
int matrice[100][100] = {
{0, 1, 0, 1},
{0, 0, 1, 0},
{0, 0, 0, 1},
{1, 0, 0, 0}
};
floydWarshall(n, matrice);
cout << „Matricea drumurilor este:\n”;
afisareMatrice(n, matrice);
return 0;
}
6. Aplicații ale Matricei Drumurilor
- Analiza conectivității:
Determinarea dacă un graf este conex sau tare conex (în cazul grafurilor orientate). - Găsirea componentelor conexe:
Matricea drumurilor poate identifica subgrafuri conexe. - Detectarea ciclurilor:
Dacă P[i][i]=1P[i][i] = 1P[i][i]=1 pentru un nod iii, graful conține cicluri. - Probleme de accesibilitate:
Verificarea dacă există un drum între două noduri.
7. Concluzie
- Matricea drumurilor este o metodă fundamentală de reprezentare a grafurilor pentru analiza conectivității.
- Se calculează eficient utilizând algoritmi precum Floyd-Warshall.
- Este utilă în probleme de accesibilitate, drumuri minime și analiza structurii grafului.