Invatare Atomica

Conexitate in grafuri neorientate

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei intelege ce inseamna conexitatea unui graf neorientat, vei invata sa identifici componentele conexe si vei implementa algoritmul de numarat componente conexe folosind DFS si BFS, cu complexitate O(V + E).

Dupa aceasta lectie vei putea:

  • Sa definesti graful conex si componenta conexa
  • Sa verifici daca un graf este conex folosind DFS sau BFS dintr-un singur nod
  • Sa numeri componentele conexe ale unui graf printr-o parcurgere repetata din noduri nevizitate
  • Sa implementezi algoritmul de numarat componente in Python (DFS recursiv si BFS cu coada)
  • Sa analizezi complexitatea O(V + E) a algoritmului si sa justifici de ce este optima
  • Sa implementezi algoritmul in C++ cu vector<vector<int>> si queue<int> EXCLUSIV INTENSIV

Incearca singur!

Provocare:

Imagineaza-ti o harta cu 7 orase. Intre unele orase exista drumuri directe: 1—2, 2—3, 3—1, 4—5, 6—7. Poti ajunge din orasul 1 in orasul 6 folosind doar drumuri existente? Dar din 4 in 5?

Deseneaza graful si identifica grupurile de orase intre care poti circula liber.

💡 Ai nevoie de un indiciu?

Urmand drumurile existente: orasele 1, 2, 3 formeaza un grup (toti conectati prin ciclul 1-2-3-1). Orasele 4 si 5 formeaza alt grup. Orasele 6 si 7 formeaza al treilea grup.

Nu poti ajunge din 1 in 6 pentru ca nu exista niciun lant de drumuri care sa le uneasca. Aceste grupuri izolate se numesc componente conexe.

1

1. Graf conex si componenta conexa — definitii

Un graf neorientat G = (V, E) este conex daca pentru oricare doua noduri u, v ∈ V exista un lant (succesiune de muchii) care le uneste.

O componenta conexa a unui graf este un subgraf conex maximal: un set de noduri intre care exista lanturi, si care nu poate fi extins cu niciun alt nod din graf pastrand aceasta proprietate.
Exemple vizuale:
Graf CONEX (1 componenta):          Graf NECONEX (3 componente):

  1 --- 2 --- 4                       1 --- 2 --- 3
  |     |
  3 --- 5 --- 6                       4 --- 5         6 --- 7

  Poti ajunge din 1 in 6:            Nu poti ajunge din 1 in 4,
  1-2-5-6 (lant de lungime 3)        nici din 5 in 7.

  Componentele grafului neconex:
    C1 = {1, 2, 3}
    C2 = {4, 5}
    C3 = {6, 7}
Proprietati esentiale:
  • Componentele conexe partitioneaza multimea nodurilor: fiecare nod apartine exact unei componente.
  • Un graf cu n noduri si 0 muchii are n componente conexe (fiecare nod izolat este propria sa componenta).
  • Un graf conex are exact 1 componenta conexa.
  • Adaugarea unei muchii intre doua componente diferite reduce numarul de componente cu 1.
2

2. Verificarea conexitatii cu un singur BFS

Idee cheie: BFS sau DFS pornind dintr-un nod sursa viziteaza exact toate nodurile accesibile din acea sursa — adica exact componenta conexa a sursei. Graful este conex daca si numai daca, pornind BFS din nodul 1, vizitam toate cele n noduri.
Algoritm verificare conexitate (pseudocod):
// Verifica daca graful cu n noduri este conex
INITIALIZEAZA vizitat[] = False pentru toti
RULEAZA BFS pornind din nodul 1
DACA numarul nodurilor vizitate == n:
    RETURNEAZA "conex"
ALTFEL:
    RETURNEAZA "neconex"

Implementare Python cu BFS:

# Verifica conexitatea cu BFS
from collections import deque

def este_conex(n, muchii):
    adj = {i: [] for i in range(1, n + 1)}
    for u, v in muchii:
        adj[u].append(v)
        adj[v].append(u)

    vizitat = set()
    coada = deque([1])
    vizitat.add(1)
    while coada:
        nod = coada.popleft()
        for vecin in adj[nod]:
            if vecin not in vizitat:
                vizitat.add(vecin)
                coada.append(vecin)
    return len(vizitat) == n

# Graf conex: 5 noduri, lant 1-2-3-4-5
print(este_conex(5, [(1,2),(2,3),(3,4),(4,5)]))
# Graf neconex: 5 noduri, 2 componente
print(este_conex(5, [(1,2),(2,3),(4,5)]))
Output real (rulat cu python):
True
False
Complexitate si optimalitate:

BFS viziteaza fiecare nod exact o data (V operatii) si examineaza fiecare muchie exact de doua ori (2E operatii). Total: O(V + E). Nu putem face mai bine: trebuie sa examinam fiecare muchie cel putin o data, deci O(V + E) este optim pentru verificarea conexitatii.

3

3. Numarat componente conexe — DFS recursiv

Ideea algoritmului: parcurgem toate nodurile 1, 2, ..., n. Cand gasim un nod nevizitat, inseamna ca am descoperit o componenta noua — incrementam contorul si rulam DFS din acel nod pentru a marca toate nodurile componentei ca vizitate. La finalul buclei, contorul contine numarul de componente.
Algoritmul pas cu pas (pseudocod):
// Numara componentele conexe
INITIALIZEAZA vizitat[] = False; nr_componente = 0
PENTRU FIECARE nod din 1 la n:
    DACA nod NU este vizitat:
        nr_componente ← nr_componente + 1
        RULEAZA DFS(nod)  // marcheaza toata componenta
RETURNEAZA nr_componente

Implementare Python cu DFS recursiv:

# DFS recursiv - marcheaza toti vecinii accesibili din 'nod'
def dfs(adj, nod, vizitat):
    vizitat[nod] = True
    for vecin in adj[nod]:
        if not vizitat[vecin]:
            dfs(adj, vecin, vizitat)

def numar_componente_dfs(n, muchii):
    adj = {i: [] for i in range(1, n + 1)}
    for u, v in muchii:
        adj[u].append(v)
        adj[v].append(u)

    vizitat = {i: False for i in range(1, n + 1)}
    nr = 0

    for nod in range(1, n + 1):
        if not vizitat[nod]:
            nr += 1
            dfs(adj, nod, vizitat)

    return nr

# Exemplu: 7 noduri, 3 componente ({1,2,3}, {4,5}, {6,7})
n = 7
muchii = [(1,2), (2,3), (4,5), (6,7)]
print("Graf:", n, "noduri, muchii =", muchii)
print("Numar componente conexe:", numar_componente_dfs(n, muchii))
Output real (rulat cu python):
Graf: 7 noduri, muchii = [(1, 2), (2, 3), (4, 5), (6, 7)]
Numar componente conexe: 3
Urmarire pas cu pas:
nod=1: nevizitat -> nr=1, DFS(1) marcheaza {1, 2, 3}
nod=2: deja vizitat -> sare
nod=3: deja vizitat -> sare
nod=4: nevizitat -> nr=2, DFS(4) marcheaza {4, 5}
nod=5: deja vizitat -> sare
nod=6: nevizitat -> nr=3, DFS(6) marcheaza {6, 7}
nod=7: deja vizitat -> sare
Rezultat final: nr = 3
4

4. Numarat componente cu BFS — varianta recomandata

Varianta cu BFS este identica ca logica cu DFS, inlocuind recursivitatea cu o coada. Este preferata in practica deoarece evita riscul de stack overflow pe grafuri cu componente adanci (Python are recursivitate limitata la ~1000 niveluri implicit). 
# BFS - numara componentele conexe
from collections import deque

def numar_componente(n, muchii):
    adj = {i: [] for i in range(1, n + 1)}
    for u, v in muchii:
        adj[u].append(v)
        adj[v].append(u)

    vizitat = {i: False for i in range(1, n + 1)}
    nr_componente = 0

    for nod in range(1, n + 1):
        if not vizitat[nod]:
            nr_componente += 1
            # BFS din nodul curent - marcheaza toata componenta
            coada = deque([nod])
            vizitat[nod] = True
            while coada:
                crt = coada.popleft()
                for vecin in adj[crt]:
                    if not vizitat[vecin]:
                        vizitat[vecin] = True
                        coada.append(vecin)

    return nr_componente

# Exemplul din lectie: 8 noduri, 3 componente
n = 8
muchii = [(1,2), (1,3), (2,4), (5,6), (7,8)]
print(f"Graf cu {n} noduri si muchiile: {muchii}")
print(f"Numar componente conexe: {numar_componente(n, muchii)}")
Output real (rulat cu python):
Graf cu 8 noduri si muchiile: [(1, 2), (1, 3), (2, 4), (5, 6), (7, 8)]
Numar componente conexe: 3
Vizualizarea grafului din exemplu:
  1 --- 2 --- 4       5 --- 6       7 --- 8
  |
  3

  Componenta 1: {1, 2, 3, 4}
  Componenta 2: {5, 6}
  Componenta 3: {7, 8}
  Numar total componente: 3
5

5. Analiza complexitatii O(V + E) — de ce este optima

Complexitate timp: O(V + E)
Bucla exterioara itereaza prin toate V nodurile. Dar nu fiecare iteratie declanseaza o parcurgere costisitoare — in total, pe intreaga executie a algoritmului:
  • Fiecare nod este adaugat in coada exact o data (la prima intalnire, cand este marcat vizitat).
  • Fiecare muchie (u, v) este examinata exact de doua ori: o data din u, o data din v.
  • Suma tuturor parcurgerilor BFS/DFS = V adaugari + 2E examinari = O(V + E).
Complexitate spatiu: O(V + E) — pentru lista de adiacenta (O(V+E)) si vectorul vizitat (O(V)).
Tabel comparativ — reprezentari si complexitate:
Reprezentare       | Spatiu    | Parcurgere BFS/DFS  | Recomandata cand
-------------------+-----------+---------------------+--------------------
Lista de adiacenta | O(V + E)  | O(V + E)            | Grafuri rare (E << V^2)
Matrice adiacenta  | O(V^2)    | O(V^2)              | V mic, E mare (dens)

La olimpiada/BAC: lista de adiacenta este MEREU preferata.
Proprietati conexitate (de memorat pentru BAC):
Graf conex cu n noduri:
  - Are cel putin n-1 muchii (exact n-1 muchii => arbore)
  - BFS/DFS dintr-un nod viziteaza toate n nodurile

Graf neconex cu n noduri si k componente:
  - BFS/DFS dintr-un nod viziteaza doar nodurile componentei sale

Numar componente = numarul de apeluri BFS/DFS din bucla exterioara
6

6. Componente conexe in C++ EXCLUSIV INTENSIV

⚡ Sectiune exclusiv pentru profilul intensiv informatica

In C++ folosim vector<vector<int>> pentru lista de adiacenta si queue<int> pentru BFS. Conventie olimpiada: indexare noduri de la 1, vector<bool> vizitat(n+1, false) pentru marcare.

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

// BFS dintr-un nod sursa - marcheaza toata componenta
void bfs(vector<vector<int>>& adj,
         vector<bool>& vizitat, int sursa) {
    queue<int> q;
    q.push(sursa);
    vizitat[sursa] = true;
    while (!q.empty()) {
        int crt = q.front(); q.pop();
        for (int vecin : adj[crt]) {
            if (!vizitat[vecin]) {
                vizitat[vecin] = true;
                q.push(vecin);
            }
        }
    }
}

int main() {
    int n = 8;
    vector<vector<int>> adj(n + 1);

    // Muchiile grafului (neorientat: adaugam in ambele directii)
    auto addEdge = [&](int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    };
    addEdge(1,2); addEdge(1,3); addEdge(2,4);
    addEdge(5,6); addEdge(7,8);

    vector<bool> vizitat(n + 1, false);
    int nr_componente = 0;

    for (int nod = 1; nod <= n; nod++) {
        if (!vizitat[nod]) {
            nr_componente++;
            bfs(adj, vizitat, nod);
        }
    }

    cout << "Graf cu " << n
         << " noduri si muchiile: {1-2, 1-3, 2-4, 5-6, 7-8}"
         << "\n";
    cout << "Numar componente conexe: "
         << nr_componente << "\n";
    cout << "Este conex: "
         << (nr_componente == 1 ? "da" : "nu") << "\n";
    return 0;
}
Output real (compilat g++ -std=c++17, apoi rulat):
Graf cu 8 noduri si muchiile: {1-2, 1-3, 2-4, 5-6, 7-8}
Numar componente conexe: 3
Este conex: nu
Diferente C++ fata de Python:
Python                          C++ (intensiv)
--------------------------------+----------------------------------
deque([nod])                     queue<int> q; q.push(nod);
coada.popleft()                  q.front(); q.pop();
vizitat = {i: False ...}         vector<bool> vizitat(n+1, false);
adj = {i: [] for ...}            vector<vector<int>> adj(n+1);
adj[u].append(v)                 adj[u].push_back(v);

Logica algoritmului este identica in ambele limbaje — diferenta este sintaxa si tipizarea explicita a lui C++.

Exercitii practice

Exercitiul 1 (Nivel minim) — Identificare manuala componente

Considera graful neorientat cu 9 noduri si muchiile: (1,2), (2,3), (1,3), (4,5), (5,6), (7,8), (8,9).

  1. Deseneaza graful (noduri ca cercuri, muchii ca linii).
  2. Identifica fiecare componenta conexa (care noduri sunt in aceeasi componenta).
  3. Este graful conex? Justifica.
  4. Ce se intampla daca adaugam muchia (3,4)? Dar muchia (6,7)?

Raspuns asteptat: 3 componente — {1,2,3}, {4,5,6}, {7,8,9}. Adaugarea lui (3,4) uneste primele doua; adaugarea lui (6,7) uneste ultimele doua.

Exercitiul 2 (Nivel standard) — Implementare si testare

Implementeaza in Python functia componente(n, muchii) care returneaza o lista de liste, fiecare sublista continand nodurile unei componente conexe (sortate crescator).

Testeaza cu:

componente(7, [(1,2),(2,3),(4,5),(6,7)])
# Asteptat: [[1, 2, 3], [4, 5], [6, 7]]

componente(5, [])
# Asteptat: [[1], [2], [3], [4], [5]]

Indiciu: modifica algoritmul din atomul 4 pentru a retine si nodurile fiecarei componente, nu doar contorul.

Exercitiul 3 (Nivel performanta) — Muchii critice EXCLUSIV INTENSIV

O muchie critica (pod) intr-un graf conex este o muchie a carei eliminare deconecteaza graful (creste numarul de componente conexe).

Implementeaza in C++ sau Python functia este_critica(n, muchii, u, v) care returneaza true daca muchia (u,v) este critica. Algoritm: elimina muchia (u,v) din graf si verifica daca graful ramane conex (numarul de componente devine mai mare decat 1).

Exemplu: Graf 1-2-3 (lant). Muchiile (1,2) si (2,3) sunt critice. Intr-un ciclu 1-2-3-1, nicio muchie nu e critica. Complexitate acceptabila: O(V + E) per verificare.

Ce ai invatat astazi

  • Un graf neorientat este conex daca intre oricare doua noduri exista un lant
  • O componenta conexa este un subgraf conex maximal; multimea nodurilor se partitioneaza in componente
  • Conexitatea se verifica cu un singur BFS/DFS: daca viziteaza toate n nodurile, graful este conex
  • Numarul de componente se calculeaza in O(V + E): bucla prin toate nodurile, BFS/DFS din fiecare nevizitat
  • Vectorul vizitat garanteaza ca fiecare nod este procesat exact o data in total — de aceea O(V + E) si nu O(V * (V+E))
  • Lista de adiacenta este reprezentarea standard: O(V+E) spatiu, parcurgere O(V+E)
  • [Intensiv] In C++: vector<vector<int>> + queue<int>; logica identica cu Python

Urmatoarea lectie

Continua cu Lectia 5: Arbori — definitie, proprietati, terminologie si parcurgeri ale arborilor generali si binari.

Continua →