Structure de données [Résolu]

Signaler
Messages postés
20
Date d'inscription
mardi 14 mars 2006
Statut
Membre
Dernière intervention
13 juillet 2008
-
Messages postés
168
Date d'inscription
jeudi 28 juin 2001
Statut
Membre
Dernière intervention
18 octobre 2008
-
Boujour tous le monde;

j'ai un ptit problème avec le tri topologique

mon problème :est ce que je dois utiliser une queue ou une pile pour faire le tri de mon graphe ?

et merci d'avance

1 réponse

Messages postés
168
Date d'inscription
jeudi 28 juin 2001
Statut
Membre
Dernière intervention
18 octobre 2008
7
Salut,

La structure va dépendre de l'algorithme que tu vas implémenter.

La pile sera à préférer si tu fais un parcours en profondeur de ton graphe et que tu empiles un noeud une fois tous ses successeurs visités => l'ordre d'empilement sera un tri topologique inverse. Il te suffit de dépiler pour obtenir l'ordre "normal".

La file est préférable si tu commences avec le premier noeud sans prédécesseur, tu l'enfiles et le retire du graphe. Tu recommence jusqu'à ce que le graphe n'ait plus de noeud. => Tu obtiendras ton tri en défilant.

a+