Définition

Le tri topologique est un algorithme qui s'applique aux graphes orientés sans cycle (DAG - Directed Acyclic Graph). Il arrange tous les nœuds du graphe dans une séquence linéaire telle que pour tout arc connectant deux nœuds (u, v), le nœud u précède le nœud v dans la séquence.

Implémentation de l'algorithme

Le processus du tri topologique suit deux étapes fondamentales :

1. Identifier les nœuds sans prédécesseurs (c'est-à-dire les nœuds avec un degré d'entrée égal à 0) et les ajouter à la séquence;
2. Supprimer ces nœuds du graphe ainsi que tous les arcs qui en partent.

Cette approche fonctionne car le premier élément de la séquence doit nécessairement être un nœud sans prédécesseurs. Une fois ces nœuds initiaux placés, leurs successeurs devinenent candidats pour la suite de la séquence. En réduisant le degré d'entrée des nœuds voisins à chaque étape, de nouveaux nœuds sans prédécesseurs émergent progressivement jusqu'à ce que tous les nœuds soient ordonnancés.

Exemples d'implémentation

Problème 1: Chemin le plus long dans un DAG

Ce problème consiste à déterminer la longueur du chemin le plus long menant à chaque nœud d'un graphe. La solution utilise le tri topologique avec une mise à jour des profondeurs maximales lors du parcours.

#include<iostream>
#include<vector>
#include<queue>
#define TAILLE_MAX 1000010
using namespace std;

int nombre_noeuds, nombre_arcs;
vector<pair<int, int>> graphe[TAILLE_MAX];
int profondeur[TAILLE_MAX], degre_entree[TAILLE_MAX];

void effectuer_tri_topologique() {
    queue<int> file_attente;
    
    for (int i = 1; i <= nombre_noeuds; i++) {
        if (degre_entree[i] == 0) {
            file_attente.push(i);
            profondeur[i] = 1;
        }
    }
    
    while (!file_attente.empty()) {
        int noeud_actuel = file_attente.front();
        file_attente.pop();
        
        for (auto& voisin : graphe[noeud_actuel]) {
            int noeud_voisin = voisin.first;
            profondeur[noeud_voisin] = profondeur[noeud_actuel] + 1;
            degre_entree[noeud_voisin]--;
            
            if (degre_entree[noeud_voisin] == 0) {
                file_attente.push(noeud_voisin);
            }
        }
    }
}

int main() {
    cin >> nombre_noeuds >> nombre_arcs;
    
    for (int i = 0; i < nombre_arcs; i++) {
        int source, destination;
        cin >> source >> destination;
        graphe[source].push_back({destination, 1});
        degre_entree[destination]++;
    }
    
    effectuer_tri_topologique();
    
    for (int i = 1; i <= nombre_noeuds; i++) {
        cout << profondeur[i] << endl;
    }
    
    return 0;
}

Problème 2: Propagation dans un réseau de neurones

Ce problème modélise un réseau de neurones où chaque nœud a un seuil d'activation. L'algorithme calcule les valeurs finales des nœuds de sortie après porpagation.

#include<iostream>
#include<vector>
#include<queue>
#define TAILLE_MAX 1010
using namespace std;

typedef long long entier;
entier nombre_noeuds, nombre_arcs;
entier activation[TAILLE_MAX], seuil[TAILLE_MAX];
entier degre_entree[TAILLE_MAX], degre_sortie[TAILLE_MAX];
vector<pair<int, entier>> graphe[TAILLE_MAX];

void effectuer_tri_topologique() {
    queue<int> file_attente;
    
    for (int i = 1; i <= nombre_noeuds; i++) {
        if (degre_entree[i] == 0) {
            file_attente.push(i);
        }
    }
    
    while (!file_attente.empty()) {
        int noeud_actuel = file_attente.front();
        file_attente.pop();
        
        for (auto& connexion : graphe[noeud_actuel]) {
            int noeud_voisin = connexion.first;
            entier poids = connexion.second;
            
            degre_entree[noeud_voisin]--;
            
            if (activation[noeud_actuel] > 0) {
                activation[noeud_voisin] += poids * activation[noeud_actuel];
            }
            
            if (degre_entree[noeud_voisin] == 0) {
                file_attente.push(noeud_voisin);
                activation[noeud_voisin] -= seuil[noeud_voisin];
            }
        }
    }
}

int main() {
    cin >> nombre_noeuds >> nombre_arcs;
    
    for (int i = 1; i <= nombre_noeuds; i++) {
        cin >> activation[i] >> seuil[i];
        if (activation[i] > 0) {
            degre_entree[i] = 0;
        }
    }
    
    for (int i = 0; i < nombre_arcs; i++) {
        int source, destination;
        entier poids;
        cin >> source >> destination >> poids;
        graphe[source].push_back({destination, poids});
        degre_entree[destination]++;
        degre_sortie[source]++;
    }
    
    effectuer_tri_topologique();
    
    bool sortie_trouvee = false;
    
    for (int i = 1; i <= nombre_noeuds; i++) {
        if (activation[i] > 0 && degre_sortie[i] == 0) {
            sortie_trouvee = true;
            cout << i << " " << activation[i] << endl;
        }
    }
    
    if (!sortie_trouvee) {
        cout << "NULL" << endl;
    }
    
    return 0;
}

Bien que le tri topologique puisse sembler simple à première vue, sa simplicité même le rend extrêmement polyvalent. De nombreux problèmes ne révèlent pas immédiatement leur nature de DAG, mais une analyse attentive des conditions implicites peut dévoiler cette structure. Lorsque vous identifiez un problème qui peut être modélisé comme un graphe orienté sans cycle, le tri topologique devrait être considéré comme une approche potentielle.