Grafuri în C++

Ce este un Graf?

Un graf G = (V, E) constă din:

• •V - mulțimea nodurilor (vârfurilor)
• •E - mulțimea muchiilor (arcelor)

Reprezentări

Matrice de Adiacență

Copiază
1#include <iostream>
2using namespace std;
3
4const int NMAX = 100;
5int adj[NMAX][NMAX];
6int n, m; // noduri, muchii
7
8void citireMatrice() {
9    cin >> n >> m;
10    for (int i = 0; i < m; i++) {
11        int x, y;
12        cin >> x >> y;
13        adj[x][y] = 1;
14        adj[y][x] = 1; // Pentru graf neorientat
15    }
16}

Liste de Adiacență

Copiază
1#include <iostream>
2#include <vector>
3using namespace std;
4
5vector<int> adj[NMAX];
6int n, m;
7
8void citireListe() {
9    cin >> n >> m;
10    for (int i = 0; i < m; i++) {
11        int x, y;
12        cin >> x >> y;
13        adj[x].push_back(y);
14        adj[y].push_back(x); // Pentru graf neorientat
15    }
16}

Parcurgerea în Lățime (BFS)

Copiază
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6vector<int> adj[NMAX];
7bool vizitat[NMAX];
8int distanta[NMAX];
9
10void BFS(int start) {
11    queue<int> q;
12    q.push(start);
13    vizitat[start] = true;
14    distanta[start] = 0;
15    
16    while (!q.empty()) {
17        int nod = q.front();
18        q.pop();
19        cout << nod << " ";
20        
21        for (int vecin : adj[nod]) {
22            if (!vizitat[vecin]) {
23                vizitat[vecin] = true;
24                distanta[vecin] = distanta[nod] + 1;
25                q.push(vecin);
26            }
27        }
28    }
29}

Parcurgerea în Adâncime (DFS)

Varianta Recursivă

Copiază
1void DFS(int nod) {
2    vizitat[nod] = true;
3    cout << nod << " ";
4    
5    for (int vecin : adj[nod]) {
6        if (!vizitat[vecin]) {
7            DFS(vecin);
8        }
9    }
10}

Varianta Iterativă

Copiază
1void DFS_iterativ(int start) {
2    stack<int> s;
3    s.push(start);
4    
5    while (!s.empty()) {
6        int nod = s.top();
7        s.pop();
8        
9        if (!vizitat[nod]) {
10            vizitat[nod] = true;
11            cout << nod << " ";
12            
13            for (int vecin : adj[nod]) {
14                if (!vizitat[vecin]) {
15                    s.push(vecin);
16                }
17            }
18        }
19    }
20}

Componente Conexe

Copiază
1int numarComponente() {
2    int componente = 0;
3    for (int i = 1; i <= n; i++) {
4        if (!vizitat[i]) {
5            DFS(i);
6            componente++;
7        }
8    }
9    return componente;
10}