Grafuri orientate și sortare topologică în C++

Într-un graf orientat, arcul x→y permite deplasarea din x spre y, fără să presupună și sensul invers. Gradul interior numără arcele care intră, iar gradul exterior arcele care ies. Un graf orientat fără circuite se numește DAG.

Sortarea topologică ordonează vârfurile astfel încât fiecare arc să plece de la un vârf aflat mai devreme spre unul aflat mai târziu. Este utilă pentru dependențe: înainte de a face o activitate, trebuie terminate toate activitățile de care depinde.

Cum funcționează

Matricea de adiacență nu mai este obligatoriu simetrică. La citirea arcului x→y setăm numai a[x][y]. Pentru a parcurge graful pornind dintr-un vârf, BFS sau DFS examinează doar arcele în sensul lor. Două noduri legate printr-un arc nu sunt automat accesibile unul din celălalt.

Algoritmul lui Kahn începe cu toate vârfurile de grad interior zero. Acestea nu au dependențe rămase. Scoatem un vârf din coadă, îl adăugăm la ordine și eliminăm conceptual arcele sale: micșorăm gradele interioare ale succesorilor. Un succesor care ajunge la zero devine disponibil.

Dacă prelucrăm toate vârfurile, ordinea este topologică. Dacă rămân vârfuri, există un circuit în partea rămasă. Nu este suficient să verificăm dacă inițial există un vârf cu grad zero: un graf poate conține și o componentă fără circuite, și o componentă ciclică.

Programul presupune 1 <= n <= 100, vârfuri numerotate 1..n și capete valide. Arcele repetate sunt deduplicate înainte de actualizarea gradelor, pentru ca matricea și contorii să descrie același graf. Coada este implementată prin tablou cu doi indici.

Exemplu urmărit pas cu pas

Pentru arcele 1→3, 2→3, 3→4, gradele interioare sunt 0,0,2,1. În coadă intră 1 și 2. Eliminarea lui 1 reduce gradul lui 3 la unu; eliminarea lui 2 îl reduce la zero, deci 3 devine disponibil. Apoi 4 devine disponibil.

Dacă adăugăm arcul 4→3, vârfurile 3 și 4 se blochează reciproc. După procesarea lui 1 și 2, coada se golește, dar nu toate vârfurile au fost incluse. Programul afișează CICLU în loc să pretindă că prefixul obținut este o ordine completă.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, m, a[101][101] = {}, degree[101] = {}, q[101], l = 0, r = 0;
    std::cin >> n >> m;
    for (int k = 0; k < m; ++k) {
        int x, y;
        std::cin >> x >> y;
        if (!a[x][y]) {
            a[x][y] = 1;
            ++degree[y];
        }
    }
    for (int i = 1; i <= n; ++i)
        if (degree[i] == 0)
            q[r++] = i;
    while (l < r) {
        int x = q[l++];
        for (int y = 1; y <= n; ++y)
            if (a[x][y] && --degree[y] == 0)
                q[r++] = y;
    }
    if (r < n)
        std::cout << "CICLU\n";
    else
        for (int i = 0; i < r; ++i)
            std::cout << q[i] << (i + 1 == r ? '\n' : ' ');
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n, m, l = 0, r = 0;
    std::vector<std::vector<int>> a(101, std::vector<int>(101, 0));
    std::vector<int> degree(101, 0), q(101);
    std::cin >> n >> m;
    for (int k = 0; k < m; ++k) {
        int x, y;
        std::cin >> x >> y;
        if (!a[x][y]) {
            a[x][y] = 1;
            ++degree[y];
        }
    }
    for (int i = 1; i <= n; ++i)
        if (degree[i] == 0)
            q[r++] = i;
    while (l < r) {
        int x = q[l++];
        for (int y = 1; y <= n; ++y)
            if (a[x][y] && --degree[y] == 0)
                q[r++] = y;
    }
    if (r < n)
        std::cout << "CICLU\n";
    else
        for (int i = 0; i < r; ++i)
            std::cout << q[i] << (i + 1 == r ? '\n' : ' ');
}

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

Un vârf intră în ordine numai când nu mai are predecesori neprelucrați. Astfel, orice arc către el pornește dintr-un vârf deja plasat. Dacă un subgraf finit nevid nu mai are niciun vârf de grad interior zero, urmărirea repetată a predecesorilor ajunge la un vârf repetat, deci la un circuit.

Cu matrice, timpul și memoria sunt O(n²). Cu liste de adiacență, algoritmul poate lucra în O(n+m) timp și memorie. Sortarea topologică poate avea mai multe rezultate corecte; coada simplă nu garantează cea mai mică ordine lexicografică.

Greșeli frecvente

Nu copia simetric arcele ca într-un graf neorientat. Nu micșora gradul unui succesor de mai multe ori pentru același arc. Nu confunda graful aciclic cu un arbore: un DAG poate avea mai mulți predecesori pentru un vârf.

Exersează

Găsește două ordini topologice pentru 1→3 și 2→3. Explică de ce 3 nu poate fi primul.

Rezolvare explicată: Ordinele 1,2,3 și 2,1,3 sunt ambele corecte. Vârful 3 are doi predecesori și trebuie să apară după amândoi.

Continuă să înveți

Reprezentări, BFS și DFS și complexitate.

Întrebări frecvente

Matricea unui graf orientat este simetrică?

Nu în general. Existența arcului x→y nu implică arcul y→x. Fiecare sens trebuie reprezentat conform datelor problemei.

Orice graf orientat are sortare topologică?

Nu. O ordine topologică există exact pentru grafurile orientate fără circuite. Un circuit ar cere ca fiecare vârf să fie înaintea următorului, inclusiv înaintea lui însuși.

Ce este gradul interior?

Este numărul arcelor care ajung într-un vârf. Într-o problemă de dependențe, el poate reprezenta numărul cerințelor preliminare încă nesatisfăcute.

Poate exista mai mult de o ordine corectă?

Da. Dacă două activități nu sunt constrânse una față de cealaltă, ordinea lor poate varia. Algoritmul trebuie să respecte criteriul suplimentar numai dacă enunțul îl cere.

BFS detectează automat orice circuit orientat?

Nu prin simpla existență a unui vecin deja vizitat. Detectarea circuitelor orientate cere o regulă adecvată, precum stările DFS sau numărarea vârfurilor eliminate de Kahn.