Discussion :

[Nemerle]

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...

[acacia]

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...

oui puisqu''un graphe connexe ne contient qu'une seule composante connexe

le lien est excellent même pour résoudre le second problème que pose condor

[Nemerle]

oui puisqu''un graphe connexe ne contient qu'une seule composante connexe

Mr de La Palisse?

Le problème revient en fait, en s'autorisant à échanger les lignes & les colonnes, à trouver la + grande sous-matrice nulle...

[acacia]

Mr de La Palisse?

ce n'est pas ça qui l'a tué