Grafuri

Notiuni de baza

Un graf G = (V, E) este format din:

• V = multimea nodurilor (varfurilor)
• E = multimea muchiilor (arcelor)

Graf neorientat: muchiile nu au directie — (u, v) = (v, u)

Graf orientat (digraf): arcele au directie — (u, v) ≠ (v, u)

Graf ponderat: fiecare muchie are un cost/greutate

---

Terminologie

Termen	Definitie
Grad (neorientat)	Numarul de muchii incidente unui nod
Grad intern/extern (orientat)	Nr. arce care intra/ies din nod
Lant	Secventa de noduri conectate prin muchii
Ciclu	Lant care incepe si se termina in acelasi nod
Graf conex	Intre oricare doua noduri exista un lant
Arbore	Graf conex fara cicluri cu n-1 muchii

---

Reprezentari

Matricea de adiacenta

int a[101][101] = {};   // a[i][j] = 1 daca exista muchia (i,j)
// citire:
int m; cin >> n >> m;
for (int k = 0; k < m; k++) {
    int u, v; cin >> u >> v;
    a[u][v] = 1;
    a[v][u] = 1;  // pentru neorientat
}

• Avantaj: acces O(1) la „exista muchia (i,j)?
• Dezavantaj: memorie O(n²) — ineficient pentru grafuri rare

Lista de adiacenta

#include <vector>
vector<int> adj[101];
// citire:
adj[u].push_back(v);
adj[v].push_back(u);  // neorientat

• Avantaj: memorie O(n + m)
• Dezavantaj: verificarea existentei unei muchii e O(grad)

---

Parcurgerea BFS (in latime)

Exploreaza nodurile in ordinea distantei fata de nodul sursa. Foloseste o coada.

#include <queue>
int viz[101] = {};

void bfs(int start) {
    queue<int> q;
    q.push(start);
    viz[start] = 1;
    while (!q.empty()) {
        int nod = q.front(); q.pop();
        cout << nod << " ";
        for (int vecin : adj[nod]) {
            if (!viz[vecin]) {
                viz[vecin] = 1;
                q.push(vecin);
            }
        }
    }
}

Utilitate: drumul cel mai scurt (in muchii) intr-un graf neponderat.

---

Parcurgerea DFS (in adancime)

Exploreaza cat mai adanc posibil pe fiecare ramura. Foloseste recursivitate (sau stiva).

int viz[101] = {};

void dfs(int nod) {
    viz[nod] = 1;
    cout << nod << " ";
    for (int vecin : adj[nod]) {
        if (!viz[vecin])
            dfs(vecin);
    }
}

Utilitate: detectarea componentelor conexe, sortare topologica.

---

Componente conexe

int nrComp = 0;
for (int i = 1; i <= n; i++) {
    if (!viz[i]) {
        nrComp++;
        dfs(i);  // sau bfs(i)
    }
}
cout << "Componente conexe: " << nrComp;

---

La examen

• Citeste atent: neorientat (adaugi muchia in ambele directii) sau orientat (o singura directie)
• BFS → distante minime; DFS → componente, ciclu, ordine topologica
• La matricea de adiacenta pentru n mare (>1000) → foloseste lista de adiacenta
• Intotdeauna initializeaza viz[] cu 0 inainte de parcurgere