Composantes Connexes
BFS/DFS pour trouver toutes les composantes
Enonce
Trouver toutes les composantes connexes d'un graphe non orienté. Retourner une liste de listes de sommets.
G = {0:[1,2], 1:[0], 2:[0], 3:[4], 4:[3], 5:[]} — 3 composantes.
Signature attendue
def composantes_connexes(G: dict) -> list:Exemple
composantes_connexes({0:[1,2], 1:[0], 2:[0], 3:[4], 4:[3], 5:[]})→[[0, 1, 2], [3, 4], [5]]
📖 Rappel de cours
Un graphe non orienté peut être partitionné en composantes connexes : des sous-graphes où tout sommet est relié à tout autre par un chemin.
Algorithme :
Pour chaque sommet non visité, lancer un BFS/DFS et collecter tous les sommets atteignables : c'est une composante connexe.
Complexité :
$O(|V| + |E|)$
Chaque sommet et chaque arête est traité(e) exactement une fois au total.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- BFS et DFS
- Algorithme de Dijkstra
- Détection de Cycle dans un Graphe Non Orienté
- Tri Topologique
- Algorithme de Bellman-Ford
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.