|

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

  1. Noduri: Se reprezintă ca o colecție de elemente distincte (o listă, un vector, un tablou etc.).
  2. 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

AvantajeDezavantaje
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

  1. Modelarea rețelelor: Lista nodurilor poate reprezenta entitățile (ex.: computere, orașe) dintr-o rețea.
  2. Graful gol: Reprezentarea unui graf fără conexiuni, utilă pentru inițializări.
  3. 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.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *