Arbres et arborescences couvrants

Algorithmes de recherche d'un arbre couvrant ou d'une arborescence

Parcours

Sert partout. On les reverra plus tard, ici juste définition et utilisation comme arbre couvrant /arborescence.

Largeur

Profondeur

Kruskal

TBD sans valuation. Comme composantes connexes (sans ordre)

TBD Kruskal. On le fait :

1. en ajoutant des arêtes en restant sans cycle : algo glouton. On prouve la minimalité par échange.
2. on optimise en montrant que c'est de la connexité. si 2 composantes connexes arbre on peut les lier et on reste arbre
3. on implémente çe avec des couleurs (attention à la mise à jour)
4. calcul de complexité $\mathcal{O}(n^2\log(n))$ s'il faut trier, et $\mathcal{O}(n^2)$ sinon. Le calcul est tricky : que n mise à jour des couleurs.