Différences

Ci-dessous, les différences entre deux révisions de la page.

--- les_fiches_revisions:algorithmique:algo_graphes [2021/01/12 10:52]
lf created
+++ les_fiches_revisions:algorithmique:algo_graphes [2021/01/14 11:03] (Version actuelle)
lf
@@ Ligne 1: / Ligne 1: @@
-en cours par fl
+======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|}}

Wiki NSI

Outils pour utilisateurs

Outils du site

Différences

Outils de la page