Diamètre d'un Arbre
Deux BFS successifs — une astuce élégante
Enonce
Implémenter diametre(G) qui calcule le diamètre d'un arbre par la technique des deux BFS.
Tester sur quelques arbres : un chemin (le diamètre vaut $n - 1$), une étoile (diamètre $2$), et un arbre quelconque.
Signature attendue
def diametre(G: dict) -> int:Exemple
diametre({0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3]})→4
📖 Rappel de cours
Le diamètre d'un arbre (ou plus généralement d'un graphe non orienté) est la plus longue des plus courtes distances entre deux sommets : $\text{diam}(G) = \max_{u, v} d(u, v)$.
Algorithme naïf :
BFS depuis chaque sommet et garder le maximum → $O(|V| \cdot (|V| + |E|))$.
Astuce des deux BFS (pour un arbre) :
- BFS depuis n'importe quel sommet $s$ → on note $u$ le sommet le plus éloigné
- BFS depuis $u$ → la distance maximale obtenue est le diamètre
Total : 2 BFS, donc $O(|V| + |E|)$ — drastiquement plus rapide.
Pourquoi ça marche :
Lemme : dans un arbre, le sommet le plus éloigné de n'importe quel sommet est toujours une extrémité d'un diamètre. La preuve repose sur l'unicité des chemins dans un arbre.
Attention : ce raccourci ne marche que pour les arbres (pas pour les graphes avec cycles).
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Représentations d'un Graphe
- Test de Bipartisme
- Détection de Cycle (graphe orienté)
- Algorithme de Floyd-Warshall
- Composantes Fortement Connexes (Kosaraju)
- Algorithme A* sur Grille
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.