Arbres binaires de recherche - Mohamed Amine EL AFRIT

Soit G un graphe orienté, on appelle racine de G un sommet r tel que, pour tous sommets x distincts de r, il existe un chemin de r vers x. .... dans le graphe. Ainsi le parcours en profondeur résout le test de connexité en temps linéaire. ..... On démontre ( voire cours + td ) que la complexité en moyenne est en O (2n log n).