Algorithmes sur les graphes

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