Grafuri în C++ - Introducere și Parcurgeri

Ce este un Graf?

Un graf este o structură formată din:

• •Noduri (vârfuri) - puncte
• •Muchii (arce) - conexiuni între noduri

Tipuri de Grafuri

• •Neorientat: muchiile nu au direcție
• •Orientat: arcele au direcție (săgeți)
• •Ponderat: muchiile au costuri/greutăți

Reprezentarea Grafurilor

1. Matrice de Adiacență

Copiază
1int a[101][101]; // 1 dacă există muchie, 0 altfel
2int n, m;        // n = noduri, m = muchii
3
4// Citire graf neorientat
5cin >> n >> m;
6for (int i = 1; i <= m; i++) {
7    int x, y;
8    cin >> x >> y;
9    a[x][y] = 1;
10    a[y][x] = 1; // Pentru graf neorientat
11}

2. Liste de Adiacență (Recomandat)

Copiază
1#include <vector>
2vector<int> vecini[101];
3
4// Citire
5for (int i = 1; i <= m; i++) {
6    int x, y;
7    cin >> x >> y;
8    vecini[x].push_back(y);
9    vecini[y].push_back(x);
10}

Parcurgerea BFS (Breadth-First Search)

Parcurgere "în lățime" - nivel cu nivel.

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

Utilizări BFS:

• •Drum minim în graf neponderat
• •Verificare conexitate
• •Parcurgere pe niveluri

Parcurgerea DFS (Depth-First Search)

Parcurgere "în adâncime" - explorează cât mai departe.

Copiază
1vector<int> vecini[101];
2bool vizitat[101];
3
4void DFS(int nod) {
5    vizitat[nod] = true;
6    cout << nod << " "; // Procesare nod
7    
8    for (int vecin : vecini[nod]) {
9        if (!vizitat[vecin]) {
10            DFS(vecin);
11        }
12    }
13}

Utilizări DFS:

• •Componente conexe
• •Detectare cicluri
• •Sortare topologică

Probleme Clasice

Numărul de componente conexe

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

Verificare graf bipartit

Copiază
1// Colorare cu BFS în 2 culori
2// Dacă reușește = bipartit

Exerciții BAC

1. •Afișează nodurile accesibile din nodul X
2. •Calculează distanța minimă între două noduri
3. •Verifică dacă graful este conex
4. •Numără componentele conexe

---

Pregătește grafurile pentru BAC cu un profesor de informatică specializat!