Discussion :

[pikachu56]

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 :



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



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



Merci pour votre aide !

[pseudocode]

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.

[Alp]

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