[Graphes] Algorithme pour transformer un graphe en graphe fortement connexe

Bonjour,

Je recherche un algorithme qui me permettrait, en ajoutant UN NOMBRE MINIMUM d'arcs, de passer d'un graphe à un graphe fortement connexe.
(A noter qu'il n'y a pas de composantes fortement connexes présentes dans mon graphe)

Voici un exemple :

Graphe d'origine :

http://admteam5.free.fr/images/graphe01.png

Graphe fortement connexe avec un nombre d'arcs ajoutés non optimisé :

http://admteam5.free.fr/images/graphe02.png

Graphe fortement connexe avec un nombre d'arcs ajoutés optimisé (Ce que je recherche) :

http://admteam5.free.fr/images/graphe03.png

Merci pour votre aide ! 8-)

A première vue, je dirais qu'il faut construire une chaine entre toutes les composantes, en reliant le puits d'une composante a la source d'une autre.

Je ne vois pas de cas où l'on pourrait faire mieux en terme de nombre d'arcs.

Si ça peut aider : http://www.developpez.net/forums/d68...exite-graphes/ :)