Graphe orienté et parcours en largeur

Version imprimable

15/08/2015, 16h08
slim_java

Graphe orienté et parcours en largeur

salut,

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

Citation:

http://rperrot.developpez.com/articl...mple_graph.png http://rperrot.developpez.com/articl...s/list_adj.png

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.
16/08/2015, 01h45
Flodelarab
Bonjour :coucou:
- 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.
16/08/2015, 01h57
slim_java
Citation:
Envoyé par Flodelarab

La liste d'adjacence ne te dispensera pas de faire une file des sommets à traiter comme il le fait brillamment.
peux tu me convaincre ? ;)
16/08/2015, 14h46
Flodelarab

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

http://img15.hostingpics.net/pics/111981essaie.png

Code:

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

17/08/2015, 18h21
Flodelarab

Citation:

Code:

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! :D

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.
18/08/2015, 15h10
picodev

Bonjour,

Slim_java, ton algo n'est pas un algo car tu ne donnes déjà pas les entrées (ce sur quoi on travaille) mais on peut deviner que ton algo prend en entrée un graphe. Et le problème est là : on effectue un parcours en largeur à partir d'un nœud car suivant le nœud de départ le parcours n'est pas le même (un graphe non connexe donne le contre exemple le plus simple). Conclusion ton essai ne donne pas un parcours en largeur tout simplement parce que tu parcoures tous les nœuds.