Invatare Atomica

Grafuri — Complet (DFS / BFS)

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei stapani grafurile de la reprezentare pana la parcurgeri DFS si BFS, cu aplicatii directe la problemele tip BAC: componente conexe, distante minime, detectie cicluri — toate implementate si verificate in C++.

Dupa aceasta lectie vei putea:

  • Sa reprezentati un graf prin lista de adiacenta in C++ cu vector<vector<int>>
  • Sa implementati DFS recursiv si sa-l aplicati pentru componente conexe si detectie cicluri
  • Sa implementati BFS cu coada si sa calculati distante minime intr-un graf neponderat
  • Sa identificati tipul problemei de graf dintr-un subiect BAC si sa alegeti algoritmul corect
  • Sa scrieti codul C++ complet in timpul examenului pornind de la schema prezentata

Incearca singur!

Provocare initiala:

Ai graful neorientat cu nodurile {1,2,3,4,5,6} si muchiile: 1-2, 1-3, 2-4, 3-4, 4-5, 5-6. Scrie ordinea in care DFS (pornind din nodul 1, vecini crescator) viziteaza nodurile.

💡 Indiciu

DFS merge cat mai adanc pe primul vecin nevizitat.

Raspuns: 1, 2, 4, 3, 5, 6 (verificat cu g++ -std=c++17).

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);}
    }
}

Exercitii practice

Exercitiul 1 (Nivel minim) — Componente conexe

Graf neorientat, n=5, muchii: 1-2, 2-3, 4-5. Scrie pe hartie ordinea DFS si numarul de componente conexe. Implementeaza in C++ si verifica.

Raspuns:
Componente: 2  (componenta 1: {1,2,3}  |  componenta 2: {4,5})

Exercitiul 2 (Nivel standard) — Distanta minima tip BAC

Graf neorientat, 7 noduri, muchii: 1-2, 1-4, 2-3, 3-5, 4-5, 5-6, 6-7. Determinati distanta minima de la nodul 1 la nodul 7 si un lant de lungime minima. Explicati de ce BFS garanteaza distanta minima (nu DFS).

Analiza BFS:
dist[1]=0, dist[2]=1, dist[4]=1, dist[3]=2, dist[5]=2, dist[6]=3, dist[7]=4
Distanta minima 1->7 = 4. Lant: 1-4-5-6-7 sau 1-2-3-5-6-7.

Exercitiul 3 (Nivel performanta) — Problema completa tip Subiect III BAC

Graf neorientat, n≤100, m muchii. Scrieti program C++ complet: (a) conex sau nu; (b) numar componente conexe; (c) distanta minima de la nodul 1 la fiecare nod.

Solutie completa C++:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int NMAX=105;
vector<int> adj[NMAX];
bool viz[NMAX]; int d[NMAX],n,m;
void dfs(int u){viz[u]=true;for(int v:adj[u])if(!viz[v])dfs(v);}
void bfs(int src){
    fill(d+1,d+n+1,-1);
    queue<int> q; d[src]=0; q.push(src);
    while(!q.empty()){int u=q.front();q.pop();
        for(int v:adj[u])if(d[v]==-1){d[v]=d[u]+1;q.push(v);}}
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){int u,v;cin>>u>>v;adj[u].push_back(v);adj[v].push_back(u);}
    int comp=0;
    for(int i=1;i<=n;i++) if(!viz[i]){comp++;dfs(i);}
    cout<<(comp==1?"CONEX":"NECONEX")<<"
";
    cout<<"Componente: "<<comp<<"
";
    bfs(1);
    for(int i=2;i<=n;i++) cout<<"dist[1]["<<i<<"] = "<<d[i]<<"
";
    return 0;
}

Ce ai invatat astazi

  • Terminologia de baza: nod, muchie, grad, lant, ciclu, conexitate, arbore
  • Reprezentarea prin lista de adiacenta cu vector<vector<int>> in C++
  • DFS recursiv O(n+m): componente conexe si detectie cicluri
  • BFS cu coada O(n+m): distanta minima in grafuri neponderate
  • Regula de decizie: distanta minima → BFS; componente sau cicluri → DFS
  • Schema C++ completa adaptabila la orice problema BAC cu grafuri

Urmatoarea lectie

Continua cu Strategii pentru Examen — time management, ordinea rezolvarii si tehnici de verificare.

Continua →