Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

======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

===A quoi ça sert ?===

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.

==== Le parcours en largeur ====

<code>
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
</code>

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 {{:les_fiches_revisions:algorithmique:image_wiki_nsi.png?400|}}