Arbres DFS et Classification des Arêtes

Lors de l'exploration en profondeur (DFS) d'un graphe orienté connexe, on génère une structure arborescente appelée arbre DFS. La topologie de cet arbre dépend entièrement de l'ordre de visite des sommets, ce qui implique qu'un même graphe peut produire plusieurs arbres DFS valides. Les arêtes constitutives de cet arbre sont nommées arêtes d'arbre.

Les arêtes n'appartenant pas à l'arbre DFS sont classées en trois catégories distinctes :

• Arêtes avant : relient un sommet à l'un de ses ancêtres dans l'arbre DFS.
• Arêtes arrière : relient un sommet à l'un de ses descendants dans l'arbre DFS.
• Arêtes transversales : relient des sommets qui ne partagent aucune relation d'ancêtre ou de descendant.

Il est crucial de noter que les arêtes transversales entre deux sous-arbres sont strictement unidirectionnelles : si le sous-arbre A est exploré avant le sous-arbre B, aucune arête transversale ne peut être dirigée de A vers B.

Définitions Fondamentales

• Composante Fortement Connexe (SCC) : Un sous-graphe maximal d'un graphe orienté dans lequel chaque paire de sommets est mutuellement accessible par des chemins dirigés.
• Point d'Articulation : Dans un graphe non orienté, un sommet dont la suppression (ainsi que ses arêtes incidentes) augmente le nombre de composantes connexes du graphe.
• Pont : Une arête dont la suppression augmente le nombre de composantes connexes du graphe.

Algorithme de Tarjan pour les Composantes Fortement Connexes

L'algorithme s'appuie sur un parcours DFS unique et utilise une pile pour mémoriser les sommets visités qui n'ont pas encore été assignés à une composante fortement connexe identifiée.

Pour chaque sommet u, on maintient deux métriques :

• disc[u] : Le temps de découverte (ou horodatage) du sommet u.
• low[u] : Le temps de découverte le plus petit accessible depuis u en empruntant au plus une arête non-arbre vers un sommet présent dans la pile.

#include <vector>
#include <stack>
#include <algorithm>

class TarjanSCC {
private:
    std::vector<std::vector<int>> adj;
    std::vector<int> disc, low;
    std::vector<bool> inStack;
    std::stack<int> nodeStack;
    int timer;

    void dfs(int u) {
        disc[u] = low[u] = ++timer;
        nodeStack.push(u);
        inStack[u] = true;

        for (int v : adj[u]) {
            if (disc[v] == 0) {
                dfs(v);
                low[u] = std::min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = std::min(low[u], disc[v]);
            }
        }

        if (low[u] == disc[u]) {
            while (true) {
                int topNode = nodeStack.top();
                nodeStack.pop();
                inStack[topNode] = false;
                if (topNode == u) break;
            }
        }
    }

public:
    TarjanSCC(int n, const std::vector<std::vector<int>>& graph) 
        : adj(graph), disc(n + 1, 0), low(n + 1, 0), inStack(n + 1, false), timer(0) {
        for (int i = 1; i <= n; ++i) {
            if (disc[i] == 0) dfs(i);
        }
    }
};

Analyse et Réflexions sur l'Algorithme SCC

1. Pourquoi la boucle principale est-elle correcte ?
À la fin de chaque appel DFS initial, la pile est vidée des sommets formant la SCC courante. Les SCC déjà traitées sont effectivement "retirées" du graphe, garantissant qu'aucune interférence ne se produit entre les différentes composantes et que la pile est toujours vide avant d'explorer une nouvelle composante connexe.

2. Pourquoi limiter low à une seule arête non-arbre ?
Sans cette restriction, la mise à jour de low pourrait créer des dépendances circulaires ou des effets de bord imprévisibles lors de la remontée dans l'arbre DFS, rendant l'évaluation dynamique invalide.

Algorithme de Tarjan pour les Points d'Articulation

Un sommet u (qui n'est pas la racine de l'arbre DFS) est un point d'articulation s'il possède un enfant v tel que low[v] >= disc[u]. Pour la racine de l'arbre DFS, elle est considérée comme un point d'articulation si et seulement si elle possède au moins deux enfants dans l'arbre DFS.

void findArticulationPoints(int u, int parent, const std::vector<std::vector<int>>& adj, 
                            std::vector<int>& disc, std::vector<int>& low, 
                            std::vector<bool>& isArticulation, int& timer) {
    disc[u] = low[u] = ++timer;
    int children = 0;

    for (int v : adj[u]) {
        if (disc[v] == 0) {
            children++;
            findArticulationPoints(v, u, adj, disc, low, isArticulation, timer);
            low[u] = std::min(low[u], low[v]);
            
            if (parent != -1 && low[v] >= disc[u]) {
                isArticulation[u] = true;
            }
        } else if (v != parent) {
            low[u] = std::min(low[u], disc[v]);
        }
    }

    if (parent == -1 && children > 1) {
        isArticulation[u] = true;
    }
}

Algorithme de Tarjen pour les Ponts

Une arête (u, v) est un pont si low[v] > disc[u]. Il est crucial d'ignorer l'arête retour vers le parent direct. Dans les multigraphes (graphes avec arêtes multiples entre deux mêmes sommets), il faut identifier les arêtes par leur identifiant unique plutôt que par les nœuds qu'elles relient pour éviter de faux positifs.

void findBridges(int u, int parentEdgeId, const std::vector<std::vector<std::pair<int, int>>>& adj, 
                 std::vector<int>& disc, std::vector<int>& low, 
                 std::vector<bool>& isBridge, int& timer) {
    disc[u] = low[u] = ++timer;

    for (auto [v, edgeId] : adj[u]) {
        if (edgeId == parentEdgeId) continue;

        if (disc[v] == 0) {
            findBridges(v, edgeId, adj, disc, low, isBridge, timer);
            low[u] = std::min(low[u], low[v]);
            if (low[v] > disc[u]) {
                isBridge[edgeId] = true;
            }
        } else {
            low[u] = std::min(low[u], disc[v]);
        }
    }
}

Nuances sur la Mise à Jour de low et disc

Lorsqu'on traite une arête retour vers un sommet déjà visité, on met à jour low[u] = min(low[u], disc[v]). Utiliser low[v] au lieu de disc[v] fonctionne pour les SCC et les ponts, mais échoue pour les points d'articulation. En effet, utiliser low[v] pourrait masquer le fait que le chemin vers un ancêtre passe obligatoirement par u, faussant ainsi la condition low[v] >= disc[u] et omettant des points d'articulation valides.

Composantes Biconnexes

Composantes Biconnexes par Arêtes (e-DCC)

Une approche consiste à identifier d'abord les ponts, puis à parcourir le graphe en les ignorant. Une méthode plus directe adapte l'algorithme SCC en ignorant simplement l'arête parente lors du parcours.

void findEdgeBiconnectedComponents(int u, int parentEdgeId, const std::vector<std::vector<std::pair<int, int>>>& adj, 
                                   std::vector<int>& disc, std::vector<int>& low, 
                                   std::stack<int>& st, std::vector<std::vector<int>>& eDCC, int& timer) {
    disc[u] = low[u] = ++timer;
    st.push(u);

    for (auto [v, edgeId] : adj[u]) {
        if (edgeId == parentEdgeId) continue;
        if (disc[v] == 0) {
            findEdgeBiconnectedComponents(v, edgeId, adj, disc, low, st, eDCC, timer);
            low[u] = std::min(low[u], low[v]);
        } else {
            low[u] = std::min(low[u], disc[v]);
        }
    }

    if (low[u] == disc[u]) {
        std::vector<int> component;
        while (true) {
            int topNode = st.top();
            st.pop();
            component.push_back(topNode);
            if (topNode == u) break;
        }
        eDCC.push_back(component);
    }
}

Composantes Biconnexes par Sommets (v-DCC)

Deux composantes biconnexes par sommets partagent au plus un sommet, qui est nécessairement un point d'articulation. Le sommet avec le temps de découverte (disc) le plus petit dans une v-DCC est soit un point d'articulation, soit la racine de l'arbre DFS.

void findVertexBiconnectedComponents(int u, int parentEdgeId, const std::vector<std::vector<std::pair<int, int>>>& adj, 
                                     std::vector<int>& disc, std::vector<int>& low, 
                                     std::stack<int>& st, std::vector<std::vector<int>>& vDCC, int& timer) {
    disc[u] = low[u] = ++timer;
    st.push(u);
    int children = 0;

    for (auto [v, edgeId] : adj[u]) {
        if (edgeId == parentEdgeId) continue;
        if (disc[v] == 0) {
            children++;
            findVertexBiconnectedComponents(v, edgeId, adj, disc, low, st, vDCC, timer);
            low[u] = std::min(low[u], low[v]);
            
            if (low[v] >= disc[u]) {
                std::vector<int> component;
                int topNode;
                do {
                    topNode = st.top();
                    st.pop();
                    component.push_back(topNode);
                } while (topNode != v);
                component.push_back(u);
                vDCC.push_back(component);
            }
        } else {
            low[u] = std::min(low[u], disc[v]);
        }
    }
}

Considérations Pratiques et Optimisations

• Pour les e-DCC, les boucles (self-loops) ne posent généralement pas de problème, mais les arêtes multiples doivent être gérées via des identifiants d'arêtes. Évitez les structures de données lourdes comme les tables de hachage pour détecter les arêtes multiples ; préférez le stockage par identifiant ou la liste d'adjacence avec indices.
• Pour les v-DCC, les arêtes multiples n'impactent pas la logique fondamentale, mais les boucles doivent être gérées avec soin lors de la construction du graphe pour éviter des comportements inattendus.
• Lors de l'utilisation de la technique de masquage de bits pour identifier les arêtes inverses (ex: edgeId ^ 1), assurez-vous que les identifiants d'arêtes commencent à un index pair (généralement 2) pour que l'opération XOR fonctionne correctement.