Sortarea topologică

Sortarea topologică este o ordonare a nodurilor unui graf orientat aciclic (DAG) astfel încât pentru orice muchie u → v, nodul u apare înainte de v în ordine.

Este ca și cum ai avea un set de sarcini cu dependențe și vrei să le faci într-o ordine validă.

Problema

Avem n sarcini. Unele depind de altele (ex: “sarcina 3 trebuie făcută înainte de sarcina 5”). Găsim o ordine validă de execuție.

Exemplu: curs universitar

Dependențe (cursuri obligatorii înainte):
Algoritmi → Structuri de date
Matematică → Algoritmi
Matematică → Analiză
Analiză → Algoritmi

Ordine validă: Matematică, Analiză, Algoritmi, Structuri de date.

Reprezentarea grafului

Folosim o listă de adiacență: pentru fiecare nod, lista nodurilor în care “duce”.

vector<int> adj[100001];  // adj[u] = lista vecinilor lui u
int gradIntrare[100001];   // câte muchii intră în nod

// Pentru fiecare muchie u → v:
adj[u].push_back(v);
gradIntrare[v]++;

Gradul de intrare al unui nod = numărul de muchii care intră în el (numărul de “dependențe” pe care le are).

Algoritmul lui Kahn (BFS)

Ideea

1. Găsim nodurile cu grad de intrare 0 (sarcini fără dependențe) - le putem face imediat.
2. Le adăugăm într-o coadă.
3. Când procesăm un nod, îl adăugăm în ordinea finală și scădem gradul de intrare al vecinilor săi.
4. Dacă un vecin ajunge cu gradul 0, îl adăugăm în coadă.
5. Repetăm până se golește coada.

Cod

#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

vector<int> adj[100001];
int gradIntrare[100001];
int n, m;

int main()
{
    fin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
        gradIntrare[v]++;
    }

    queue<int> q;

    // Adăugăm nodurile cu grad de intrare 0
    for (int i = 1; i <= n; i++)
        if (gradIntrare[i] == 0)
            q.push(i);

    vector<int> ordine;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ordine.push_back(u);

        for (int v : adj[u]) {
            gradIntrare[v]--;
            if (gradIntrare[v] == 0)
                q.push(v);
        }
    }

    // Dacă nu am procesat toate nodurile, există ciclu
    if ((int)ordine.size() != n) {
        fout << "CICLU - imposibil";
    } else {
        for (int x : ordine)
            fout << x << " ";
    }

    return 0;
}

date.in:

6 6
1 2
1 3
2 4
3 4
4 5
4 6

date.out:

1 2 3 4 5 6

(Sau orice altă ordine validă)

Pas cu pas

Graful:

1 → 2 → 4 → 5
1 → 3 → 4 → 6

Grad de intrare inițial: | Nod | Grad | |—|—| | 1 | 0 | | 2 | 1 | | 3 | 1 | | 4 | 2 | | 5 | 1 | | 6 | 1 |

Pasul 1: adăugăm nodurile cu grad 0

Coadă: [1]

Pasul 2: procesăm 1

Adăugăm în ordine: [1]. Scădem gradul vecinilor săi (2 și 3).

Coadă: [2, 3]

Pasul 3: procesăm 2

Ordine: [1, 2]. Scădem gradul lui 4.

Coadă: [3]

Pasul 4: procesăm 3

Ordine: [1, 2, 3]. Scădem gradul lui 4.

Coadă: [4]

Pasul 5: procesăm 4

Ordine: [1, 2, 3, 4]. Scădem gradul lui 5 și 6.

Coadă: [5, 6]

Pasul 6 și 7: procesăm 5 și 6

Ordine finală: [1, 2, 3, 4, 5, 6].

Detectarea ciclurilor

Dacă la final numărul de noduri din ordine < n, graful conține un ciclu și sortarea topologică este imposibilă.

Exemplu cu ciclu:
1 → 2 → 3 → 1

Niciun nod nu are grad 0 (toți au măcar o dependență), deci coada rămâne goală imediat.

Aplicații practice

1. Planificarea cursurilor

Cursurile cu dependențe (precedentele necesare) - găsim o ordine validă.

2. Compilarea unui proiect

Fișierele care se includ unul pe altul. Trebuie compilate în ordinea dependențelor.

3. Execuția instrucțiunilor într-un program

Unele operații trebuie făcute înainte de altele. Scheduler-ul face sortare topologică.

4. Dicționar extraterestru

Primim o listă de cuvinte în ordinea alfabetică a unei limbi necunoscute. Găsim ordinea literelor.

Varianta cu DFS

Există și o variantă cu DFS: parcurgem graful, iar nodurile se adaugă la final în ordine inversă a terminării lor.

vector<int> adj[100001];
bool vizitat[100001];
vector<int> ordine;

void dfs(int u) {
    vizitat[u] = true;
    for (int v : adj[u])
        if (!vizitat[v])
            dfs(v);
    ordine.push_back(u);
}

int main() {
    // ...
    for (int i = 1; i <= n; i++)
        if (!vizitat[i])
            dfs(i);

    // Inversăm ordinea
    reverse(ordine.begin(), ordine.end());
}

Ambele abordări dau o sortare topologică validă (pot diferi ordinea efectivă).

Complexitate

n = număr noduri, m = număr muchii.

Exemplu: ordine cursuri

#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

vector<int> adj[101];
int gradIntrare[101];
int n, m;

int main()
{
    fin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        fin >> a >> b;
        // a trebuie făcut înainte de b
        adj[a].push_back(b);
        gradIntrare[b]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (gradIntrare[i] == 0)
            q.push(i);

    int procesate = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        fout << u << " ";
        procesate++;

        for (int v : adj[u]) {
            gradIntrare[v]--;
            if (gradIntrare[v] == 0)
                q.push(v);
        }
    }

    if (procesate < n)
        fout << "\nImposibil - exista ciclu";

    return 0;
}

Greșeli frecvente

1. Direcția muchiilor

// "a trebuie făcut înainte de b"
adj[a].push_back(b);  // a → b
gradIntrare[b]++;

Dacă inversezi direcția, obții ordinea inversă (validă tot pentru o altă interpretare).

2. Uitarea verificării de ciclu

Dacă graful are ciclu, coada se golește înainte să procesăm toate nodurile. Verifică la final că ordine.size() == n.

3. Lista de adiacență greșit dimensionată

Declară vector<int> adj[MAXN] global cu dimensiune suficientă.

Ce să reții

• Sortarea topologică = ordonare a nodurilor dintr-un DAG astfel încât dependențele sunt respectate.
• Kahn (BFS): găsim nodurile cu grad 0, le procesăm, scădem gradul vecinilor.
• DFS: parcurgem graful, adăugăm la final, inversăm ordinea.
• Complexitate O(n + m).
• Dacă nu procesăm toate nodurile, graful are ciclu - sortare imposibilă.
• Aplicații: cursuri, compilare, scheduler, dependențe.