Méthode de malgrange (améliorée) pour chercher les composantes fortement connexes d'un graphe orienté
Description
Ce code implémente une classe de recherche de composantes fortement connexes d'un graphe orienté quelconque. J'ai utilisé la méthode de Malgrange un petit peu améliorée au niveau du calcul de la puissance de la matrice associée (au lieu de calculer M^k, je calcule (I+M)^(2^i) qui permet d'avoir une complexité moins importante : O(n^4) contre O(n^3*log(n)).
L'interêt est bien sur de trouver ces composantes très rapidement en entrant les successeurs des sommets de votre graphe et il les affiche.
J'implémenterais peut-être une interface graphique un jour parce que le mode console c'est moyen pour du C++ ^^
Voila, comme d'habitude je suis ouvert à toutes remarques/critiques/améliorations etc. :)
L'interêt est bien sur de trouver ces composantes très rapidement en entrant les successeurs des sommets de votre graphe et il les affiche.
J'implémenterais peut-être une interface graphique un jour parce que le mode console c'est moyen pour du C++ ^^
Voila, comme d'habitude je suis ouvert à toutes remarques/critiques/améliorations etc. :)
Codes Sources
A voir également
- Méthode de malgrange (améliorée) pour chercher les composantes fortement connexes d'un graphe orienté
- Composante fortement connexe - Forum C++ & C++ .NET
- Méthode ramzi - Forum C# / .NET
- Méthode mathématique pour gagner au keno - Forum PHP
- Méthode tbl - Forum Javascript / DHTML
- Graphe connexe - Forum Java
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.