Discussion :

[slim_java]

salut,

En lisant ce cours sur DVP.com , j'ai compris que pour tout graphes orienté on peut lui associé une liste d’adjacence

ce qui m'étonne ici, c'est qu' au niveau du parcours en largeur de ce graphe, l'auteur a utilisé une fille d'attente FIFO
pour afficher les noeuds du graphe
au lieu de travailler directement avec la liste d'adjacence .
je comprend pas pourquoi ce choix surtout que dans toute la documentation que j'ai pu trouver , on répète la même procédure et on explique la liste adjacence sans l'utiliser dans tel parcours.
je me demande que si en travaillant avec la liste d'adg sans utiliser une FIFO, on obtient peut être
pas l'affichage qu'on souhaite !! ou il y a peut être un autre problème qui m’échappe. pouvez vous m'orienter ?
merci pour vos réponse.

[Flodelarab]

Bonjour

• Je n'aime pas son exemple car son premier tour de boucle est en dehors de la boucle.
• Cependant, il n'y a pas de problème avec la liste d'adjacence. Elle est utilisée juste dans l'ellipse (ce qu'il ne détaille pas), ou non (on n'est pas obligé de fabriquer une liste d'adjacence avant de faire un parcours en largeur). Il ne parle pas de la façon dont il fait la liste des enfants du sommet.
• La liste d'adjacence ne te dispensera pas de faire une file des sommets à traiter comme il le fait brillamment.

[slim_java]

• La liste d'adjacence ne te dispensera pas de faire une file des sommets à traiter comme il le fait brillamment.

peux tu me convaincre ?

[Flodelarab]

Oui. Donne la méthode que tu emploies à partir de la liste d'adjacence.

[slim_java]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
pour i de 1 a n faire
p=liste [i]
   tant que(p && p!= marqué)
      visiter (p)
      marquer(p)
     p=p->suivant;
  fin tant que
fin pour

[Flodelarab]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

p!= marqué

Qu'est-ce que c'est que ça ? Ton noeud n'est pas marqué et n'a pas a être marqué. Ni ta liste d'adjacence. Tu as donc créé une liste dont tu nies l'existence!

De plus, tu prends comme base de travail la liste d'adjacence qui n'a aucune raison de reprendre l'ordre nécessaire pour un parcours en largeur.