Ceci est une ancienne révision du document !
Il existe 2 méthodes pour parcourir un graphe :
•Le parcours en largeur
•le parcours en profondeur
•Chercher une chaine dans un graphe
Les parcours d'algorithmes permettent de voir les liens entre eux entre différents éléments. L'idée du “parcours” est de “visiter” tous les sommets d'un graphe en partant d'un sommet quelconque.
VARIABLE G : un graphe s : noeud (origine) u : noeud v : noeud f : file (initialement vide) //On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine DEBUT s.couleur ← noir enfiler (s,f) tant que f non vide : u ← defiler(f) pour chaque sommet v adjacent au sommet u : si v.couleur n'est pas noir : v.couleur ← noir enfiler(v,f) fin si fin pour fin tant que FIN
Voyez ce programme comme une tache d'encre qui s'étend.
Le programme va d'abord visiter les taches adjacentes au point de départ pour visiter ceux de plus en plus loin.
Si on part du point I on aura un ordre de visite de: I , E , H , C , D , G , H , B , F et A
La distance entre le point I et celui visité est indiqué sur le graphe ci dessous
Dans le cas du parcours en profondeur, on va chercher à aller “le plus loin possible”.
La méthode de découverte est unidirectionnelle.
VARIABLE G : un graphe u : noeud v : noeud //On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine DEBUT PARCOURS-PROFONDEUR(G,u) : u.couleur ← noir pour chaque sommet v adjacent au sommet u : si v.couleur n'est pas noir : PARCOURS-PROFONDEUR(G,v) fin si fin pour FIN
Qu'est qu'un cycle ?
Un cycle est tout simplement une boucle dans un graphe, c'est utile pour savoir s'il est possible d'effectuer un parcours qui revient à son point de départ sans être obligé de faire demi-tour.
L'algorithme ci dessous permet de “détecter” la présence d'au moins un cycle dans un graphe.
VARIABLE s : noeud (noeud quelconque) G : un graphe u : noeud v : noeud p : pile (vide au départ) //On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine DEBUT CYCLE(): piler(s,p) tant que p n'est pas vide : u ← depiler(p) pour chaque sommet v adjacent au sommet u : si v.couleur n'est pas noir : piler(v,p) fin si fin pour si u est noir : renvoie Vrai sinon : u.couleur ← noir fin si fin tant que renvoie Faux FIN
Ici nous cherchons à connaitre le chemin entre deux noeuds
cet algorithme renvoie un chemin, ce n'est pas forcement le plus court
VARIABLE G : un graphe start : noeud (noeud de départ) end : noeud (noeud d'arrivé) u : noeud chaine : ensemble de noeuds (initialement vide) DEBUT TROUVE-CHAINE(G, start, end, chaine): chaine = chaine ⋃ start //le symbol ⋃ signifie union, il permet d'ajouter le noeud start à l'ensemble chaine si start est identique à end : renvoie chaine fin si pour chaque sommet u adjacent au sommet start : si u n'appartient pas à chaine : nchemin = TROUVE-CHAINE(G, u, end, chaine) si nchemin non vide : renvoie nchemin fin si fin si fin pour renvoie NIL FIN