Invatare Atomica

Aplicatii grafuri: Probleme rezolvate

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei consolida toate algoritmii pe grafuri invatati prin rezolvarea unor probleme complete de tip Bacalaureat si concurs: distante minime, componente conexe, reconstructia drumului si (la intensiv) distante in grafuri ponderate cu Dijkstra.

Dupa aceasta lectie vei putea:

  • Sa alegi algoritmul potrivit (BFS/DFS) pentru o problema data
  • Sa calculezi distanta minima intre doua noduri folosind BFS
  • Sa numeri si sa identifici componentele conexe ale unui graf
  • Sa reconstruiesti drumul minim retinand parintele fiecarui nod
  • Sa detectezi existenta unui ciclu intr-un graf orientat
  • Sa rezolvi probleme complete asa cum apar la Bacalaureat

Incearca singur!

Provocare:

Ai un graf cu nodurile 1-5 si muchiile: (1,2), (1,3), (2,4), (3,5). Fara a scrie cod, raspunde: care este distanta minima de la nodul 1 la nodul 5? Dar la nodul 4? Care algoritm folosesti si de ce?

💡 Ai nevoie de un indiciu?

BFS (parcurgere in latime) gaseste drumul cu cel mai mic numar de muchii intr-un graf neponderat. Pornesti din nodul 1 si explorezi vecinii nivel cu nivel.

Nodul 5 se atinge prin lantul 1-3-5 (2 muchii). Nodul 4 se atinge prin 1-2-4 (2 muchii). Ambele sunt la distanta 2.

1

1. Strategia: ce algoritm alegem?

Inainte de a scrie cod, trebuie sa identificam tipul problemei si sa alegem algoritmul potrivit:
Tabel de decizie
Cerinta problemei Algoritm Complexitate
Distanta minima (nr. muchii), graf neponderat BFS O(V + E)
Componente conexe, existenta drumului DFS sau BFS O(V + E)
Detectare ciclu in graf orientat DFS cu colorare O(V + E)
Distanta minima, graf ponderat pozitiv Dijkstra O((V+E) log V)

Unde V = numar noduri, E = numar muchii.

Reprezentarea grafului in Python

In toate problemele urmatoare vom folosi lista de adiacenta ca dictionar:

# Graf neorientat cu 6 noduri
graf = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6],
    4: [2],
    5: [2, 6],
    6: [3, 5]
}

Muchii: 1-2, 1-3, 2-4, 2-5, 3-6, 5-6

2

2. Problema 1: Distanta minima cu BFS

Enunt: Intr-un graf neorientat cu 6 noduri si muchiile: 1-2, 1-3, 2-4, 2-5, 3-6, 5-6, determina distanta minima (in numar de muchii) de la nodul 1 la toate celelalte noduri.
Traseul BFS nivel cu nivel

Nivelul 0: {1} — nodul de start, distanta 0

Nivelul 1: {2, 3} — vecini nevizitati ai lui 1, distanta 1

Nivelul 2: {4, 5, 6} — vecini nevizitati ai lui 2 si 3, distanta 2

# BFS - distante minime de la un nod sursa
from collections import deque

def bfs_distante(graf, start):
    dist = {start: 0}
    coada = deque([start])
    while coada:
        nod = coada.popleft()
        for vecin in graf[nod]:
            if vecin not in dist:
                dist[vecin] = dist[nod] + 1
                coada.append(vecin)
    return dist

graf = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6],
    4: [2],
    5: [2, 6],
    6: [3, 5]
}

dist = bfs_distante(graf, 1)
print("Distanta minima de la 1 la 6:", dist[6])
for nod in sorted(dist):
    print(f"  nod {nod}: distanta {dist[nod]}")
Output real (rulat cu python):
Distanta minima de la 1 la 6: 2
  nod 1: distanta 0
  nod 2: distanta 1
  nod 3: distanta 1
  nod 4: distanta 2
  nod 5: distanta 2
  nod 6: distanta 2
Analiza complexitatii

Fiecare nod este adaugat in coada o singura data: O(V). Fiecare muchie este examinata de doua ori (o data din fiecare capat): O(E). Total: O(V + E).

3

3. Problema 2: Componente conexe cu DFS

Enunt: Dat un graf neorientat cu 8 noduri si muchiile: 1-2, 1-3, 4-5, 7-8, determina numarul componentelor conexe si nodurile din fiecare componenta. (Nodurile 6 este izolat — nu are muchii.)
Idee algoritm

Parcurgem toate nodurile. Daca un nod nu a fost vizitat inca, lansam un DFS din el — toate nodurile atinse de acel DFS formeaza o componenta conexa. Repetam pentru urmatorul nod nevizitat.

# DFS - componente conexe
def dfs(graf, nod, vizitat, componenta):
    vizitat.add(nod)
    componenta.append(nod)
    for vecin in graf[nod]:
        if vecin not in vizitat:
            dfs(graf, vecin, vizitat, componenta)

def componente_conexe(graf):
    vizitat = set()
    componente = []
    for nod in sorted(graf):
        if nod not in vizitat:
            comp = []
            dfs(graf, nod, vizitat, comp)
            componente.append(sorted(comp))
    return componente

graf = {
    1: [2, 3], 2: [1], 3: [1],
    4: [5], 5: [4],
    6: [],
    7: [8], 8: [7]
}

comps = componente_conexe(graf)
print("Numar componente conexe:", len(comps))
for i, c in enumerate(comps, 1):
    print(f"  Componenta {i}: {c}")
Output real (rulat cu python):
Numar componente conexe: 4
  Componenta 1: [1, 2, 3]
  Componenta 2: [4, 5]
  Componenta 3: [6]
  Componenta 4: [7, 8]
Nota: DFS recursiv vs. limite de stiva

Recursivitatea DFS poate atinge limita de stiva Python pentru grafuri cu mii de noduri. In practica (si la examene), pentru grafuri mici aceasta implementare este acceptabila. Pentru grafuri mari se foloseste versiunea iterativa cu stiva explicita.

4

4. Problema 3: Reconstructia drumului minim

Enunt: Pe acelasi graf cu 6 noduri, determina nu doar distanta, ci si drumul concret (lista de noduri) de la nodul 1 la nodul 6 cu numar minim de muchii.
Tehnica: vectorul parinte

In BFS, cand descoperim un nod v prin nodul u, retinem parinte[v] = u. Dupa ce ajungem la destinatie, mergem inapoi prin parinti pana la sursa, inversam lista si obtinem drumul.

# BFS cu reconstructia drumului
from collections import deque

def bfs_drum(graf, start, stop):
    parinte = {start: None}
    coada = deque([start])
    while coada:
        nod = coada.popleft()
        if nod == stop:
            break
        for vecin in graf[nod]:
            if vecin not in parinte:
                parinte[vecin] = nod
                coada.append(vecin)
    if stop not in parinte:
        return []  # nu exista drum
    # Reconstructia: mergem inapoi prin parinti
    drum = []
    nod = stop
    while nod is not None:
        drum.append(nod)
        nod = parinte[nod]
    return list(reversed(drum))

graf = {
    1: [2, 3], 2: [1, 4, 5],
    3: [1, 6], 4: [2],
    5: [2, 6], 6: [3, 5]
}

drum = bfs_drum(graf, 1, 6)
print("Drum minim de la 1 la 6:", drum)
print("Lungimea drumului:", len(drum) - 1, "muchii")
Output real (rulat cu python):
Drum minim de la 1 la 6: [1, 3, 6]
Lungimea drumului: 2 muchii

Drumul 1 → 3 → 6 are 2 muchii, care este minimul (exista si drumul 1→2→5→6 cu 3 muchii).

5

5. Problema 4: Detectarea ciclului intr-un graf orientat

Enunt: Dat un graf orientat, determina daca acesta contine un ciclu. Exemplu 1: 1→2→3→1 (ciclu). Exemplu 2: 1→2→3 (aciclic, fara ciclu).
Tehnica: colorare tricolora in DFS

Fiecare nod primeste una din trei culori:

  • 0 (alb) — nod nevizitat
  • 1 (gri) — nod descoperit, DFS inca in curs pentru el
  • 2 (negru) — nod complet explorat

Un arc catre un nod gri inseamna ciclu (arc inapoi in arborele DFS).

# Detectare ciclu in graf orientat
def are_ciclu(graf, n):
    # 0=nevizitat, 1=in_stiva, 2=finalizat
    culoare = [0] * (n + 1)

    def dfs(nod):
        culoare[nod] = 1
        for vecin in graf.get(nod, []):
            if culoare[vecin] == 1:
                return True  # arc catre nod gri = ciclu
            if culoare[vecin] == 0:
                if dfs(vecin):
                    return True
        culoare[nod] = 2
        return False

    for nod in range(1, n + 1):
        if culoare[nod] == 0:
            if dfs(nod):
                return True
    return False

# Graf orientat cu ciclu: 1->2->3->1
graf_ciclu = {1: [2], 2: [3], 3: [1]}
print("Graf 1->2->3->1 are ciclu:", are_ciclu(graf_ciclu, 3))

# Graf orientat fara ciclu: 1->2->3
graf_aciclic = {1: [2], 2: [3], 3: []}
print("Graf 1->2->3 are ciclu:", are_ciclu(graf_aciclic, 3))
Output real (rulat cu python):
Graf 1->2->3->1 are ciclu: True
Graf 1->2->3 are ciclu: False
6

6. Problema 5: Distante minime in graf ponderat — Dijkstra EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

Algoritmul lui Dijkstra rezolva problema drumurilor minime intr-un graf ponderat cu costuri pozitive. Este un algoritm Greedy: la fiecare pas extrage nodul cu distanta estimata minima si relaxeaza muchiile acestuia. Complexitate: O((V+E) log V) cu min-heap.

Enunt

Graf neorientat ponderat cu 5 noduri. Muchii cu costuri: (1,2,4), (1,3,2), (2,3,5), (2,4,1), (3,5,8), (4,5,3). Determina distantele minime de la nodul 1 la toate celelalte noduri.

Implementare Python (heapq):

import heapq

def dijkstra(graf, start, n):
    dist = {i: float('inf') for i in range(1, n+1)}
    dist[start] = 0
    heap = [(0, start)]   # (distanta, nod)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue   # intrare depasita in heap
        for cost, v in graf.get(u, []):
            if dist[u] + cost < dist[v]:
                dist[v] = dist[u] + cost
                heapq.heappush(heap, (dist[v], v))
    return dist

# graf[u] = [(cost, v), ...]  - neorientat: adaugam ambele directii
graf = {
    1: [(4,2), (2,3)],
    2: [(4,1), (5,3), (1,4)],
    3: [(2,1), (5,2), (8,5)],
    4: [(1,2), (3,5)],
    5: [(8,3), (3,4)]
}

dist = dijkstra(graf, 1, 5)
print("Distante minime de la nodul 1:")
for nod in sorted(dist):
    print(f"  nod {nod}: {dist[nod]}")
Output real (rulat cu python):
Distante minime de la nodul 1:
  nod 1: 0
  nod 2: 4
  nod 3: 2
  nod 4: 5
  nod 5: 8

Verificare manuala: 1→3 (cost 2), 3→? → 5: calea 1→3→5 are cost 2+8=10, dar 1→2→4→5 are cost 4+1+3=8. Deci dist[5]=8. Corect.

Implementare C++ cu priority_queue:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

void dijkstra(int start, int n,
              vector<vector<pair<int,int>>>& adj,
              vector<int>& dist) {
    dist.assign(n + 1, INT_MAX);
    dist[start] = 0;
    // min-heap: (distanta, nod)
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<pair<int,int>>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [cost, v] : adj[u]) {
            if (dist[u] + cost < dist[v]) {
                dist[v] = dist[u] + cost;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n = 5;
    vector<vector<pair<int,int>>> adj(n + 1);
    // adj[u] = {cost, v}
    adj[1].push_back({4,2}); adj[2].push_back({4,1});
    adj[1].push_back({2,3}); adj[3].push_back({2,1});
    adj[3].push_back({5,2}); adj[2].push_back({5,3});
    adj[2].push_back({1,4}); adj[4].push_back({1,2});
    adj[3].push_back({8,5}); adj[5].push_back({8,3});
    adj[4].push_back({3,5}); adj[5].push_back({3,4});

    vector<int> dist;
    dijkstra(1, n, adj, dist);

    cout << "Distante minime de la nodul 1:" << endl;
    for (int i = 1; i <= n; i++) {
        cout << "  nod " << i << ": "
             << (dist[i] == INT_MAX ? -1 : dist[i]) << endl;
    }
    return 0;
}
Output real (compilat g++ -std=c++17, apoi rulat):
Distante minime de la nodul 1:
  nod 1: 0
  nod 2: 4
  nod 3: 2
  nod 4: 5
  nod 5: 8

Python si C++ produc acelasi rezultat — algoritmul este identic, doar sintaxa difera.

Exercitii practice

Exercitiul 1 (Nivel minim) — Traseu BFS pe hartie

Considera graful cu nodurile 1-5 si muchiile: 1-2, 2-3, 2-4, 4-5. Simuleaza BFS pornind din nodul 1 si completeaza tabelul: ce noduri intra in coada la fiecare pas si care este distanta lor fata de nodul 1? Raspunde: care este distanta de la 1 la 5?

Exercitiul 2 (Nivel standard) — Componente conexe, problema completa

Scrie in Python o functie care primeste numarul de noduri n si o lista de muchii, construieste lista de adiacenta si returneaza numarul de componente conexe. Testeaza cu: n=7, muchii=[(1,2),(3,4),(3,5),(6,7)]. Raspuns asteptat: 3 componente conexe (nodurile 1-2, 3-4-5, 6-7).

Exercitiul 3 (Nivel performanta) — Drum minim cu reconstructie + verificare ciclu

Dat un graf orientat cu 6 noduri si arcele: 1→2 (cost 3), 1→3 (cost 1), 3→2 (cost 1), 2→4 (cost 2), 4→5 (cost 4), 5→6 (cost 1), 6→3 (cost 1). (a) Exista un ciclu? (b) Care este drumul de cost minim de la 1 la 4? Scrie codul complet in Python si explica de ce Dijkstra (nu BFS) este necesar.

Ce ai invatat astazi

  • Cum sa alegi algoritmul potrivit (BFS/DFS/Dijkstra) in functie de cerinta problemei
  • BFS pentru distante minime in nr. de muchii — O(V+E)
  • DFS pentru componente conexe — un DFS per componenta
  • Tehnica vectorului parinte pentru reconstructia drumului minim
  • Detectarea ciclului in graf orientat cu colorare tricolora (0/1/2)
  • [Intensiv] Dijkstra cu min-heap pentru grafuri ponderate — O((V+E) log V)

Modulul completat!

Ai parcurs toate cele 6 lectii ale modulului Teoria Grafurilor. Revino la index pentru a revizui sau a trece la modulul urmator.

Inapoi la modul →