Différences

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

--- les_fiches_revisions:algorithmique:algo_graphes [2021/01/12 11:58]
lf
+++ les_fiches_revisions:algorithmique:algo_graphes [2021/01/14 10:36]
lf
@@ Ligne 40: / Ligne 40: @@
 \\
 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
+La distance entre le point I et celui visité est indiqué sur le graphe {{:les_fiches_revisions:algorithmique:image_wiki_nsi.png?400|}}
-{{: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
@@ Ligne 63: / Ligne 62: @@
     fin si
   fin pour
+FIN
+</code>
+Sur ce graphe on peut voir le chemin pris par l'algorithme.
+{{:les_fiches_revisions:algorithmique:algo_graphe.png?400|}}
+\\
+\\
+====Cycle dans les graphes====
+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.
+<code>
+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
 </code>
+====Chercher une chaine dans un graphe====
+Ici nous cherchons à connaitre le chemin entre deux noeuds\\
+:!: cet algorithme renvoie un chemin, ce n'est pas forcement le plus court
-FIXME **METTRE IMAGE ICI FIXME
+<code>
+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
+</code>

Wiki NSI

Outils pour utilisateurs

Outils du site

Différences

Outils de la page