Discussion :

[cyspeo]

Bonjour,
Je suis en train de concevoir un alogo me permettant de parcourir toutes les tables reliées de près ou de loin à une tables de départ.
J'ai pensé utilisé un graphe pour représenter le schéma de ma base de donnée.
J'obtient un graphe orienté avec :
- les noeuds pour représenter les tables
- les arrêtes sortant du neud pour représenter une ForeignKey
- les arrêtes entrant sur le noeud pour représenter les ImportedForeignKey (FK des autres tables pointant vers la table du noeud).


Je voulait utiliser un arbre couvrant pour parcourir tous les neuds une seule fois à partir d'un noeud de départ, mais le problème c'est que mon graphe est orienté donc pas d'arbre possible.

Avez une idée pour parcourir tous les noeuds une seule fois se trouvant sur les chamins menant à un noeud choisit ?

[MABROUKI]

bonjour

La version du spannig tree pour les graphes orientes s'appele l'algorithme d'Edmonds ( Chu–Liu/Edmonds' algorithm ):
lien wiki en:
http://www.google.fr/url?q=http://en.wikipedia.org/wiki/Edmonds'_algorithm&sa=U&ei=RBeEUuidN4iytAaw-4HYDw&ved=0CB4QFjAA&usg=AFQjCNH-qXDg0jMvcIVyFnQ6LbFGziIFkw

Sur le bas de page tu as un lien vers une implementation du MIT en C++..

Bon code...

[cyspeo]

Merci pour la réponse rapide.
Je vais essayer avec cette algo.