Metode de Reprezentare a Grafurilor: Lista Nodurilor 27
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.