Introduction au tri topologique : Deux approches principales existent : l'algorithme de Kahn (basé sur BFS) et la méthode DFS. Leur objectif est d'ordonner les nœuds dans un graphe dirigé acyclique (DAG), offrant souvent plusieurs solutions valides. Ces algorithmes identifient également la présence de cycles.

Principe de l'algorithme de Kahn (BFS) : Le cœur repose sur l'initialisation des nœuds avec un degré entrant nul. Recherche de sources → exploration des voisins → ajout à la file, et ainsi de suite.

Approche DFS : L'état de visite (vis) est crucial. Le résultat obtenu est un ordre topologique inversé, donc une pile facilite le stockage. Logique : parcourir chaque nœud comme point de départ → exploration récursive avec DFS. États de vis :

• 0 : non visité
• 1 : tous les descendants traités (terminé)
• 2 : en cours de traitement (utilisé pour détecter les cycles) Transition typique : 0 → 2 → 1

Questions fréquentes : Exploration des voisins ? — Parcourir toutes les arêtes sortantes. Pourquoi un nœud avec vis=2 indique un cycle ? — vis=2 signifie que ce nœud est actuellement en cours de traitement dans la pile d'appels ; si un de ses descendants pointe vers lui, cela forme un cycle. Pourquoi Kahn utilise le degré entrant (ind) et DFS l'état vis ? — Dans Kahn, un nœud est prêt seulement quand tous ses prédecesseurs sont traités (ind[x]==0). Dans DFS, la recherche se fait en profondeur, ce qui s'oppose à l'ordre topologique standard ; donc, on utilise vis pour marquer les nœuds terminés. DFS identifie en réalité les nœuds avec un degré sortant nul, inversant ainsi la logique. Relaxation ? — Généralement associée aux plus courts chemins, mais non directement pertinente ici. Pourquoi utiliser une structure d'adjacence comme la liste chaînée statique ? — Pour parcourir efficacement les voisins lors de l'exploration (similarité avec les listes d'adjacence).

Code de l'algorithme de Kahn : Utilisation d'une liste d'adjacence (chaînée statique ou vecteur) et d'une file. Complexité temporelle : O(V + E), où V est le nombre de nœuds et E le nombre d'arêtes.

struct Arete {
    int destination, suivante;
};
Arete aretes[10008];
int tete[10008]; // tête de liste pour chaque nœud
int degreEntrant[10008];
int cycleDetecte;

void kahn(int nbNoeuds) {
    queue<int> file;
    for (int i = 1; i <= nbNoeuds; ++i) {
        if (degreEntrant[i] == 0) {
            file.push(i);
        }
    }
    int noeud, voisin;
    int compteur = 0;
    while (!file.empty()) {
        noeud = file.front();
        file.pop();
        compteur++;
        for (int idx = tete[noeud]; idx != -1; idx = aretes[idx].suivante) {
            voisin = aretes[idx].destination;
            degreEntrant[voisin]--;
            if (degreEntrant[voisin] == 0) {
                file.push(voisin);
            }
        }
    }
    if (compteur != nbNoeuds) cycleDetecte = 1;
}

Code de l'algorithme DFS : Utilisation d'une pile pour stocker l'ordre topologique inversé. Complexité temporelle : O(V + E), car chaque nœud et arête est visité une fois.

struct Arete {
    int destination, suivante;
};
Arete aretes[10008];
int tete[10008];
int visite[10008]; // 0: non visité, 1: terminé, 2: en cours
stack<int> resultat;
int cycleTrouve;

void explorer(int noeud) {
    visite[noeud] = 2;
    for (int idx = tete[noeud]; idx != -1; idx = aretes[idx].suivante) {
        int voisin = aretes[idx].destination;
        if (visite[voisin] == 0) {
            explorer(voisin);
            if (cycleTrouve) return;
        } else if (visite[voisin] == 2) {
            cycleTrouve = 1;
            return;
        }
    }
    resultat.push(noeud);
    visite[noeud] = 1;
}

Construction de la liste d'adjacence :

int compteurAretes = 0;

void ajouterArete(int source, int destination) {
    aretes[compteurAretes].destination = destination;
    aretes[compteurAretes].suivante = tete[source];
    tete[source] = compteurAretes;
    compteurAretes++;
}

Les deux algorithmes reflètent des philosophies distinctes : l'une procède par niveaux (BFS), l'autre par exploration profonde (DFS).