Différences

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

--- les_fiches_revisions:algorithmique:algo_graphes [2021/01/12 11:01]
lf
+++ les_fiches_revisions:algorithmique:algo_graphes [2021/01/12 11:58]
lf
@@ Ligne 4: / Ligne 4: @@
 •Le parcours en largeur \\
 •le parcours en profondeur
+•Chercher une chaine dans un graphe
 ===A quoi ça sert ?===
@@ Ligne 34: / Ligne 35: @@
 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 ci dessous
+{{:https://www.loutrel.fr/wikinsi/lib/exe/fetch.php?t=1610446819&w=344&h=214&tok=72b88a&media=les_fiches_revisions:algorithmique:image_wiki_nsi.png|}} FIXME
+==== Le parcours en profondeur====
+Dans le cas du parcours en profondeur, on va chercher à aller "le plus loin possible". \\
+La méthode de découverte est unidirectionnelle.\\
+\\
+<code>
+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
+</code>
+FIXME **METTRE IMAGE ICI FIXME

Wiki NSI