Composantes connexes et parcours de graphes non orientés

1. Définition des composantes connexes

Intuitivement, un graphe non orienté peut être d'un seul tenant (connexe) ou être constitué de plusieurs "morceaux" disjoints. Chacun de ces morceaux est une composante connexe.

Pour une définition plus formelle, essentielle dans le cadre de votre préparation, nous pouvons utiliser la notion de relation d'équivalence.

Pour aller plus loin dans la formalisation, sachez que l'on peut définir une relation $\mathcal{R}$ sur l'ensemble des sommets $V$ par : $u\mathcal{R}v$ si et seulement s'il existe un chemin reliant $u$ et $v$. On démontre aisément que $\mathcal{R}$ est une relation d'équivalence. Les composantes connexes sont alors simplement les classes d'équivalence de cette relation. Chaque classe regroupe tous les sommets qui sont connectés entre eux.

2. L'algorithme de calcul des composantes connexes

L'idée centrale de l'algorithme est simple et élégante. Elle repose sur une propriété fondamentale des parcours de graphe (BFS ou DFS) :
Un parcours démarré depuis un sommet $s$ visitera tous les sommets de la composante connexe de $s$, et uniquement ceux-là.

L'algorithme général s'en déduit naturellement :

1. On maintient un tableau de visités pour tous les sommets, initialisé à False.
2. On parcourt l'ensemble des sommets du graphe, disons de 0 à $|V|-1$.
3. Pour chaque sommet $i$, s'il n'a pas encore été visité :
   a. On a trouvé une nouvelle composante connexe. On incrémente un compteur de composantes.
   b. On lance un parcours (DFS ou BFS) à partir de $i$.
   c. Ce parcours marquera tous les sommets de la composante connexe de $i$ comme visités.
4. On continue jusqu'à avoir examiné tous les sommets.

La vidéo suivante détaille ce processus avec une clarté exemplaire, en utilisant le DFS.

3. Implémentation et Analyse

Voici une implémentation Python de l'algorithme, qui retourne une liste de listes, où chaque sous-liste représente les sommets d'une composante connexe. Nous utiliserons le DFS, par cohérence avec les leçons précédentes.

def find_connected_components(graph):
    """
    Trouve toutes les composantes connexes d'un graphe non orienté.
    
    Args:
        graph: Dictionnaire représentant le graphe par listes d'adjacence.
               ex: {0: [1, 2], 1: [0], 2: [0], 3: [4], 4: [3]}

    Returns:
        Une liste de listes, où chaque sous-liste contient les sommets
        d'une composante connexe.
    """
    if not graph:
        return []

    visited = set()
    all_components = []

    def _dfs(start_node, current_component):
        """Parcourt une composante connexe à partir de start_node."""
        stack = [start_node]
        visited.add(start_node)
        
        while stack:
            node = stack.pop()
            current_component.append(node)
            
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)




    # Itérer sur tous les sommets possibles (en supposant qu'ils sont nommés de 0 à n-1)
    # ou plus robustement, sur les clés du dictionnaire
    for node in graph:
        if node not in visited:



            # Ce sommet n'a pas été visité, il appartient donc à une nouvelle composante
            new_component = []
            _dfs(node, new_component)
            all_components.append(new_component)
            
    return all_components




# Exemple d'utilisation
graph_disconnected = {
    0: [1, 2],
    1: [0],
    2: [0],
    3: [4],
    4: [3],
    5: [6, 7],
    6: [5],
    7: [5]
}

components = find_connected_components(graph_disconnected)
print(f"Les composantes connexes sont : {components}")



# Output possible (l'ordre des composantes et des sommets peut varier) : 
# Les composantes connexes sont : [[0, 2, 1], [3, 4], [5, 7, 6]]

Complexité

L'analyse de complexité est un point crucial pour l'Agrégation.

• La boucle principale itère sur tous les sommets $V$.
• La fonction de parcours _dfs est appelée une seule fois pour chaque composante connexe.
• Au total, chaque sommet est ajouté à la pile et retiré une seule fois. Chaque arête $(u,v)$ est examinée deux fois (une fois depuis $u$ et une fois depuis $v$, car le graphe est non orienté).

La complexité totale de l'algorithme est donc $\mathcal{O}(|V|+|E|)$, soit linéaire par rapport à la taille du graphe.

Implémentation en OCaml

Conformément à vos objectifs, il est instructif de voir comment cet algorithme s'écrit en OCaml. L'approche est la même : une fonction principale qui itère sur les sommets et appelle un DFS récursif sur les sommets non encore visités.

4. Exercice de synthèse

Considérons le graphe non orienté suivant, représenté par sa liste d'adjacence :

G = {
    0: [4],
    1: [2, 5],
    2: [1, 5, 6],
    3: [7],
    4: [0],
    5: [1, 2, 6],
    6: [2, 5],
    7: [3, 8],
    8: [7]
}

Votre tâche (10 minutes) :

Déroulez "à la main" l'algorithme find_connected_components sur ce graphe.

1. Tenez à jour l'ensemble visited.
2. Listez les appels à _dfs.
3. Écrivez la liste finale des composantes connexes que vous obtenez.

Conclusion

La détermination des composantes connexes est une application directe et élégante des algorithmes de parcours. C'est un exemple paradigmatique de la manière dont on peut résoudre un problème global sur un graphe en itérant sur ses sommets et en lançant des explorations locales (les parcours) pour traiter des sous-structures (les composantes).

Points clés à retenir :

• Une composante connexe est un sous-graphe connexe maximal. Formellement, ce sont les classes d'équivalence de la relation "être relié par un chemin".
• L'algorithme consiste à itérer sur tous les sommets et à lancer un parcours (DFS ou BFS) depuis chaque sommet non encore visité.
• Chaque nouvel appel à un parcours depuis la boucle principale identifie une nouvelle composante connexe.
• La complexité de l'algorithme est linéaire, $\mathcal{O}(|V|+|E|)$.

Prochaine étape :
Nous avons trouvé des "îlots" de connectivité dans des graphes non orientés. Que devient cette notion de connectivité dans un graphe orienté, où les chemins sont des "rues à sens unique" ? Cela nous amènera à définir un concept plus subtil et puissant : les composantes fortement connexes. Ce sera l'objet de notre prochaine leçon.