Componente conexe în C++: etichetare prin BFS

Când este un graf conex

Un graf neorientat este conex dacă între oricare două vârfuri există un lanț de muchii. Nu cerem ca fiecare pereche să fie legată direct. De exemplu, lanțul 1-2-3 este conex chiar dacă nu există muchia 1-3. În schimb, două grupuri fără nicio legătură între ele formează un graf neconex.

O componentă conexă este un grup maximal de vârfuri între care putem circula pe muchii. Cuvântul maximal înseamnă că nu mai putem adăuga un vârf din afara grupului păstrând această proprietate. Componentele împart toate vârfurile în grupuri disjuncte: fiecare vârf aparține exact uneia.

Un vârf izolat reprezintă singur o componentă. Graful cu un singur vârf și zero muchii este conex. Pentru n vârfuri fără muchii avem exact n componente. Aceste cazuri mici sunt importante: un algoritm care pornește doar din capetele muchiilor le-ar omite.

Imagine indisponibilă: În graful cu șase vârfuri, muchiile 1-3, 2-4 și 4-6 formează componentele 1,3 și 2,4,6, iar vârful 5 este singur în a treia componentă.

De la o parcurgere la toate componentele

O parcurgere BFS descoperă exact componenta sursei. Pentru întregul graf, examinăm pe rând vârfurile 1..n. Dacă un vârf este deja etichetat, componenta lui a fost parcursă și îl sărim. Altfel, am găsit o componentă nouă: creștem contorul și pornim BFS din acel vârf.

Înlocuim tabloul boolean de vizitare cu comp. Valoarea zero înseamnă încă nevizitat. O valoare pozitivă reprezintă numărul componentei. Când adăugăm un vecin în coadă, îi atribuim imediat eticheta componentei curente. Nu resetăm acest tablou între parcurgeri, deoarece am pierde evidența componentelor descoperite.

În desen, pornirea din 1 etichetează 1 și 3 cu valoarea 1. Următorul vârf fără etichetă este 2; de acolo ajungem la 4 și 6, toate primind 2. Vârful 3 este deja rezolvat. Mai târziu, 5 pornește singur componenta 3. Etichetele în ordinea vârfurilor sunt 1 2 1 2 3 2.

Program complet în două reprezentări

Citim n m, apoi m muchii ale unui graf neorientat simplu. Limitele sunt 1 <= n <= 100 și 0 <= m <= n*(n-1)/2. Capetele sunt distincte și în 1..n; nu apar perechi repetate. Programul afișează numărul componentelor pe prima linie și eticheta fiecărui vârf pe a doua.

Matricea clasică a[101][101] are capacitate fixă. Folosim numai liniile și coloanele 1..n. Coada are indici de la zero și cel mult n elemente la o parcurgere. La începerea unei componente resetăm st și dr, reutilizând aceeași memorie. În varianta cu std::vector, matricea și tablourile auxiliare sunt dimensionate cu n+1, fără schimbarea convenției vârfurilor.

Varianta clasică, cu tablouri

#include <iostream>

int main() {
    int n, m;
    std::cin >> n >> m;
    int a[101][101] = {};
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    int comp[101] = {};
    int q[101] = {};
    int nr = 0;
    for (int s = 1; s <= n; ++s) {
        if (comp[s] != 0) continue;
        ++nr;
        int st = 0, dr = 0;
        q[dr++] = s;
        comp[s] = nr;
        while (st < dr) {
            int x = q[st++];
            for (int y = 1; y <= n; ++y) {
                if (a[x][y] && comp[y] == 0) {
                    comp[y] = nr;
                    q[dr++] = y;
                }
            }
        }
    }
    std::cout << nr << '\n';
    for (int i = 1; i <= n; ++i) {
        if (i > 1) std::cout << ' ';
        std::cout << comp[i];
    }
    std::cout << '\n';
}

Varianta echivalentă cu std::vector

#include <iostream>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> a(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    std::vector<int> comp(n + 1, 0);
    std::vector<int> q(n + 1, 0);
    int nr = 0;
    for (int s = 1; s <= n; ++s) {
        if (comp[s] != 0) continue;
        ++nr;
        int st = 0, dr = 0;
        q[dr++] = s;
        comp[s] = nr;
        while (st < dr) {
            int x = q[st++];
            for (int y = 1; y <= n; ++y) {
                if (a[x][y] && comp[y] == 0) {
                    comp[y] = nr;
                    q[dr++] = y;
                }
            }
        }
    }
    std::cout << nr << '\n';
    for (int i = 1; i <= n; ++i) {
        if (i > 1) std::cout << ' ';
        std::cout << comp[i];
    }
    std::cout << '\n';
}

Pentru intrarea 6 3, urmată de 1 3, 2 4, 4 6, ieșirea este 3, apoi 1 2 1 2 3 2. Numerele etichetelor depind de ordinea aleasă pentru porniri; aici componenta cu cel mai mic vârf neetichetat primește următorul număr.

De ce funcționează și cât costă

BFS nu poate trece într-o altă componentă, fiindcă între componente nu există muchii. În interiorul unei componente ajunge la toate vârfurile accesibile. Bucla exterioară asigură că nicio componentă nu rămâne neîncepută. Împreună, aceste observații justifică atât numărul, cât și etichetele.

Nu executăm n parcurgeri complete independente: fiecare vârf este procesat o singură dată în total. Examinăm o linie de n valori pentru fiecare vârf, deci timpul este O(n²), nu O(n³). Memoria matricei este O(n²), iar memoria auxiliară este O(n). În tabloul fix rezervăm capacitatea maximă chiar și pentru un graf mic.

Pentru a răspunde numai dacă graful este conex, este suficient să verificăm dacă rezultatul nr este 1. Pentru a afla dacă două vârfuri se pot conecta, comparăm etichetele lor. Nu comparăm gradele: două vârfuri de același grad pot aparține unor componente diferite.

Exersează

1. Câte componente are un graf cu cinci vârfuri și singura muchie 2-4?
2. Ce se strică dacă resetăm comp înaintea fiecărei porniri?
3. Pot două componente distincte să aibă o muchie între ele?

Răspunsuri: patru; pierdem vizitarea anterioară și putem număra repetat aceeași componentă; nu, acea muchie le-ar uni într-o singură componentă. În lecția despre drumuri vom măsura și numărul minim de muchii dintre două vârfuri accesibile.