Commentçamarche.net
CodeS-SourceS
Rechercher un code, un tuto, une réponse

Méthode de malgrange (améliorée) pour chercher les composantes fortement connexes d'un graphe orienté

0/5 (5 avis)

Vue 6 955 fois - Téléchargée 689 fois

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

Codes Sources

A voir également

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.