Detectarea unui ciclu în graf neorientat, în C++

Un ciclu într-un graf neorientat simplu este un traseu închis cu cel puțin trei muchii, fără repetarea celorlalte vârfuri. Muchiile 1–2, 2–3 și 3–1 formează un ciclu. O singură muchie 1–2 nu formează ciclu doar fiindcă poate fi parcursă în ambele sensuri.

Ce înseamnă DFS

DFS vine de la Depth-First Search, în română parcurgere în adâncime. Pornim dintr-un vârf și continuăm printr-un vecin nevizitat, apoi prin vecinii lui, înainte de a reveni la alte ramuri. Implementarea recursivă păstrează revenirea prin stiva apelurilor: fiecare apel așteaptă terminarea celui pe care l-a pornit.

Citim 1≤n≤100 și m muchii distincte între vârfuri diferite. Graful este simplu, fără bucle și fără muchii multiple. Afișăm DA dacă există un ciclu în oricare componentă, altfel NU. Limita n=100 păstrează mică adâncimea recursiei din exemplu.

Vecin vizitat, dar diferit de părinte

La intrarea în vârful u îl marcăm vizitat. Dacă vecinul v nu este vizitat, continuăm recursiv, indicând u drept părinte. Dacă v este deja vizitat și diferă de părinte, am găsit o închidere de ciclu.

Excludem părintele deoarece aceeași muchie apare în matrice în ambele sensuri. Muchia prin care am ajuns în u nu este o legătură nouă care închide un traseu. Pentru grafuri cu muchii multiple, identificarea doar prin vârful părinte nu ar fi suficientă; contractul de graf simplu contează.

În triunghiul 1-2-3-1, parcurgerea 1,2,3 găsește din 3 muchia spre 1, deja vizitat și diferit de părintele 2. Aceasta închide un ciclu.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int n,a[101][101]={},viz[101]={};
bool ciclu(int u,int parinte) {
    viz[u]=1;
    for(int v=1;v<=n;++v) if(a[u][v]) {
        if(!viz[v]) { if(ciclu(v,u)) return true; }
        else if(v!=parinte) return true;
    }
    return false;
}
int main() {
    int m; cin >> n >> m;
    for(int i=0;i<m;++i) { int u,v; cin >> u >> v; a[u][v]=a[v][u]=1; }
    bool exista=false;
    for(int u=1;u<=n && !exista;++u) if(!viz[u]) exista=ciclu(u,0);
    cout << (exista?"DA\n":"NU\n");
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int n; vector<vector<int>> a; vector<int> viz;
bool ciclu(int u,int parinte) {
    viz[u]=1;
    for(int v=1;v<=n;++v) if(a[u][v]) {
        if(!viz[v]) { if(ciclu(v,u)) return true; }
        else if(v!=parinte) return true;
    }
    return false;
}
int main() {
    int m; cin >> n >> m;
    a.assign(n+1,vector<int>(n+1)); viz.assign(n+1,0);
    for(int i=0;i<m;++i) { int u,v; cin >> u >> v; a[u][v]=a[v][u]=1; }
    bool exista=false;
    for(int u=1;u<=n && !exista;++u) if(!viz[u]) exista=ciclu(u,0);
    cout << (exista?"DA\n":"NU\n");
}

O componentă verificată nu înseamnă tot graful

Bucla din main pornește o parcurgere din fiecare vârf încă nevizitat. Dacă există un ciclu într-o componentă separată de vârful 1, el trebuie detectat. Ne oprim când avem deja un răspuns adevărat, deoarece cerința cere numai existența.

Pentru triunghi, după 1→2→3, vârful 3 vede muchia spre 1. Vârful 1 este vizitat și nu este părintele lui 3, care este 2. Acest lucru închide ciclul.

Matricea ocupă O(n²) memorie și fiecare vârf scanează n posibili vecini, deci timpul este O(n²+m). Stiva apelurilor poate conține O(n) apeluri. Tabloul clasic are 101×101 celule, folosind vârfurile 1..n.

Exersează

Un drum 1–2–3 produce NU, un triunghi produce DA, iar un graf fără muchii produce NU. Adaugă un vârf izolat înaintea unui triunghi separat pentru a verifica toate componentele.

Continuă cu parcurgerile grafurilor, componentele conexe și recursivitatea.

Întrebări frecvente

Ce înseamnă DFS?

DFS vine de la Depth-First Search, adică parcurgere în adâncime. Explorează o ramură prin vecini nevizitați înainte să revină la celelalte; varianta recursivă folosește stiva apelurilor pentru revenire.

De ce ignor muchia către tată la detectarea ciclurilor neorientate?

Aceeași muchie este vizibilă din ambele capete. Revenirea directă către tată prin ea nu formează un ciclu într-un graf simplu. Un alt vecin deja vizitat semnalează legătura care închide un ciclu.

Trebuie verificată fiecare componentă pentru existența unui ciclu?

Da. Un DFS pornit dintr-un singur vârf acoperă numai componenta lui. Repetă pornirea din fiecare vârf nevizitat; regula prezentată presupune graf simplu, fără muchii paralele sau bucle.