Petits ajouts concernant ces problèmes de connexités: en raffinement de l'algo donné ici pour déterminer si un graphe est connexe ou non, dans la pratique on recherche souvent en fait les composantes connexes.
On peut adapter l'algo standard d'acacia, mais il y en a d'autres plus rapides, en particulier avec de la prog parallèle, par exemple celui de Shiloach-Vishkin.
Un des liens de cette page donnait un algo ULTRA-performant (malheureusement en Fortran): http://computation.pa.msu.edu/NO/Con...sentation.html
mais ce lien n'est plus accessible! M'enfin, y a quand même les explications...
Partager