1
1. Concepte fundamentale de graf
Un graf G = (V, E) este format din multimea nodurilor V si multimea muchiilor E. La BAC apar grafuri neorientate (fara directie) si orientate (arce cu directie).
Terminologie esentiala BAC:
- Gradul unui nod = numarul de muchii incidente
- Lant = secventa u1,u2,...,uk unde fiecare pereche consecutiva e muchie
- Ciclu = lant cu primul si ultimul nod identice, fara repetare intermediara
- Graf conex = exista lant intre oricare doua noduri
- Arbore = graf conex fara cicluri; exact n-1 muchii
- Componenta conexa = submultime maxima de noduri cu lanturi intre ele
Graful din lectie vizualizat:
// 1 --- 2 (muchii: 1-2, 1-3, 2-4, 3-4, 4-5, 5-6) // | X | (ciclu existent: 1-2-4-3-1) // 3 --- 4 // | // 5 --- 6
2
2. Reprezentarea grafurilor in C++
Lista de adiacenta (recomandata la BAC):
vector<vector<int>> adj(n+1) — spatiu O(n+m). Matricea de adiacenta ocupa O(n²), ineficienta pentru grafuri rare.#include <iostream> #include <vector> using namespace std; int main() { int n = 6; vector<vector<int>> adj(n+1); adj[1]={2,3}; adj[2]={1,4}; adj[3]={1,4}; adj[4]={2,3,5}; adj[5]={4,6}; adj[6]={5}; for (int i=1; i<=n; i++) { cout << "adj[" << i << "] ="; for (int v:adj[i]) cout << " " << v; cout << " "; } return 0; }
Output real (g++ -std=c++17):
adj[1] = 2 3 adj[2] = 1 4 adj[3] = 1 4 adj[4] = 2 3 5 adj[5] = 4 6 adj[6] = 5
Citire cu cin (varianta examen):
int n, m; cin >> n >> m; vector<vector<int>> adj(n+1); for (int i=0; i<m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }
3
3. DFS — Depth First Search
DFS exploreaza cat mai adanc inainte de a reveni (backtrack). Implementare prin recursie. Complexitate O(n + m).
Logica DFS in 3 pasi:
- Marcheaza nodul curent ca vizitat; proceseaza-l
- Pentru fiecare vecin nevizitat → apeleaza recursiv DFS
- Toti vecinii vizitati → return (backtrack automat)
#include <iostream> #include <vector> using namespace std; vector<vector<int>> adj; vector<bool> visited; void dfs(int u) { visited[u] = true; cout << u << " "; for (int v : adj[u]) if (!visited[v]) dfs(v); } int main() { int n=6; adj.resize(n+1); visited.assign(n+1,false); adj[1]={2,3};adj[2]={1,4};adj[3]={1,4}; adj[4]={2,3,5};adj[5]={4,6};adj[6]={5}; cout << "DFS: "; dfs(1); cout << endl; return 0; }
Output real (g++ -std=c++17):
DFS: 1 2 4 3 5 6
Urmarire recursie:
dfs(1) -> dfs(2) -> dfs(4) -> dfs(3)[return] -> dfs(5) -> dfs(6)[return] Ordine vizitare: 1 2 4 3 5 6
4
4. BFS — Breadth First Search
BFS exploreaza nivel cu nivel. Foloseste o coada (queue). Garanteaza distanta minima in grafuri neponderate. Complexitate O(n + m).
Logica BFS in 3 pasi:
- Adauga sursa in coada; dist[sursa] = 0
- Cat timp coada nu e goala: extrage u (front + pop)
- Pentru vecin v cu dist[v]==-1: dist[v]=dist[u]+1; adauga in coada
#include <iostream> #include <vector> #include <queue> using namespace std; int main() { int n=6; vector<vector<int>> adj(n+1); adj[1]={2,3};adj[2]={1,4};adj[3]={1,4}; adj[4]={2,3,5};adj[5]={4,6};adj[6]={5}; vector<int> dist(n+1,-1); queue<int> q; dist[1]=0; q.push(1); while(!q.empty()) { int u=q.front(); q.pop(); for(int v:adj[u]) if(dist[v]==-1){dist[v]=dist[u]+1;q.push(v);} } for(int i=1;i<=n;i++) cout<<"dist["<<i<<"] = "<<dist[i]<<endl; return 0; }
Output real (g++ -std=c++17):
dist[1] = 0 dist[2] = 1 dist[3] = 1 dist[4] = 2 dist[5] = 3 dist[6] = 4
Interpretare: distanta minima de la 1 la 6 = 4. Lant: 1-2-4-5-6 (sau 1-3-4-5-6).
5
5. Componente conexe si detectia ciclurilor
Componente conexe: rulam DFS din fiecare nod nevizitat; fiecare pornire noua = o componenta. Detectie ciclu: vecin vizitat diferit de parinte implica ciclu.
#include <iostream> #include <vector> using namespace std; vector<vector<int>> adj; vector<bool> viz; bool hasCycle; void dfs(int u, int par) { viz[u]=true; for(int v:adj[u]) { if(!viz[v]) dfs(v,u); else if(v!=par) hasCycle=true; } } int main() { // Graf FARA ciclu: 1-2-3-4 int n=4; adj.resize(n+1); viz.assign(n+1,false); adj[1]={2};adj[2]={1,3};adj[3]={2,4};adj[4]={3}; hasCycle=false; dfs(1,-1); cout<<"Graf 1-2-3-4 are ciclu: "<<(hasCycle?"DA":"NU")<<endl; // Graf CU ciclu: triunghi 1-2-3-1 n=3; adj.assign(n+1,{}); viz.assign(n+1,false); adj[1]={2,3};adj[2]={1,3};adj[3]={1,2}; hasCycle=false; dfs(1,-1); cout<<"Graf 1-2-3-1 are ciclu: "<<(hasCycle?"DA":"NU")<<endl; return 0; }
Output real (g++ -std=c++17):
Graf 1-2-3-4 are ciclu: NU Graf 1-2-3-1 are ciclu: DA
Numarare componente conexe (output verificat: 3):
int comp=0; for(int i=1;i<=n;i++) if(!viz[i]){comp++;dfs(i,-1);} cout<<"Componente: "<<comp<<endl; // Graf cu {1,2,3},{4,5},{6,7} -> Componente: 3
6
6. DFS vs BFS: ghid de decizie BAC
Distanta minima → BFS. Componente sau cicluri → DFS. Alegerea gresita = puncte pierdute.
Tabel de decizie rapid:
// PROBLEMA | ALGORITM // -----------------------------|---------- // Componente conexe | DFS sau BFS // Detectie ciclu | DFS cu parametru parent // Distanta minima neponderat | BFS // Graful este conex? | DFS; verifica vizitat toate // Noduri la distanta k | BFS; numara dist[i]==k
Complexitati: DFS si BFS O(n+m). La BAC n≤1000 -> lista adiacenta mereu optima.
Schema C++ completa (copiaza si adapteaza la examen):
#include <iostream> #include <vector> #include <queue> using namespace std; const int NMAX=105; vector<int> adj[NMAX]; bool viz[NMAX]; int dist[NMAX],n,m; void dfs(int u){viz[u]=true;for(int v:adj[u])if(!viz[v])dfs(v);} void bfs(int src){ queue<int> q; dist[src]=0; viz[src]=true; q.push(src); while(!q.empty()){ int u=q.front();q.pop(); for(int v:adj[u]) if(!viz[v]){viz[v]=true;dist[v]=dist[u]+1;q.push(v);} } }