Outils pour utilisateurs
les_fiches_revisions:algorithmique:algo_graphes
Différences
Ci-dessous, les différences entre deux révisions de la page.
| Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
|
les_fiches_revisions:algorithmique:algo_graphes [2021/01/14 10:33] lf |
les_fiches_revisions:algorithmique:algo_graphes [2021/01/14 11:03] (Version actuelle) 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 \\ | 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 | + | La distance entre le point I et celui visité est indiqué sur le graphe {{: |
| - | ==== 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.\\ | ||
| - | \\ | ||
| - | < | ||
| - | VARIABLE | ||
| - | G : un graphe | ||
| - | u : noeud | ||
| - | v : noeud | ||
| - | //On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l' | ||
| - | DEBUT | ||
| - | PARCOURS-PROFONDEUR(G, | ||
| - | u.couleur ← noir | ||
| - | pour chaque sommet v adjacent au sommet u : | ||
| - | si v.couleur n'est pas noir : | ||
| - | PARCOURS-PROFONDEUR(G, | ||
| - | fin si | ||
| - | fin pour | ||
| - | FIN | ||
| - | </ | ||
| - | {{: | ||
| - | \\ | ||
| - | \\ | ||
| - | ====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' | ||
| - | L' | ||
| - | < | ||
| - | 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' | ||
| - | 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 | ||
| - | </ | ||
| - | ====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 | ||
| - | |||
| - | < | ||
| - | VARIABLE | ||
| - | G : un graphe | ||
| - | start : noeud (noeud de départ) | ||
| - | end : noeud (noeud d' | ||
| - | u : noeud | ||
| - | chaine : ensemble de noeuds (initialement vide) | ||
| - | |||
| - | DEBUT | ||
| - | TROUVE-CHAINE(G, | ||
| - | chaine = chaine ⋃ start //le symbol ⋃ signifie union, il permet d' | ||
| - | si start est identique à end : | ||
| - | renvoie chaine | ||
| - | fin si | ||
| - | pour chaque sommet u adjacent au sommet start : | ||
| - | si u n' | ||
| - | nchemin = TROUVE-CHAINE(G, | ||
| - | si nchemin non vide : | ||
| - | renvoie nchemin | ||
| - | fin si | ||
| - | fin si | ||
| - | fin pour | ||
| - | renvoie NIL | ||
| - | FIN | ||
| - | </ | ||
les_fiches_revisions/algorithmique/algo_graphes.1610616817.txt.gz · Dernière modification: 2021/01/14 10:33 de lf
Outils de la page
Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial 4.0 International
