https://wiki.goupill.fr/ 2026-06-12T06:09:43+00:00 https://wiki.goupill.fr/ https://wiki.goupill.fr/lib/exe/fetch.php?media=wiki:dokuwiki.svg text/html 2023-01-05T17:25:21+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.goupill.fr/doku.php?id=nsi:terminales:graphes:algos_graphes_non_orientes&rev=1672939521&do=diff Algorithmes pour graphes non orientés On dispose d'une classe Graph permettant de gérer un graphe. On veut le doter de méthodes supplémentaires. Votre travail est de faire les implémentations nécessaires. Recherche d'un cycle On veut définir une méthode text/html 2023-01-26T19:16:47+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.goupill.fr/doku.php?id=nsi:terminales:graphes:astar&rev=1674760607&do=diff Dijkstra amélioré : A* Vidéo en anglais La vidéo explique très bien le principe. Pour l'instant je ne fais pas d'explication supplémentaire. Heuristique Dans la vidéo, vous pouvez voir qu'on utilise une fonction pour « surélever » les nœuds. Cela permet de donner une sorte de pente qui oriente les chemins dans la direction du nœud que l'on cherche à atteindre. text/html 2021-11-08T18:46:12+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.goupill.fr/doku.php?id=nsi:terminales:graphes:cours&rev=1636397172&do=diff Graphes Définition Un graphe est composé de sommets -- vertex -- liés par des arêtes -- edges. On pourra noter $G(\mathcal{S}, \mathcal{A})$ pour désigner le graphe G qui possède un ensemble S de sommets et un ensemble A d'arêtes -- en anglais, G(V, E), pour vertex et $\mathcal{S} = \lbrace A, B, C, D, E\rbrace$$\mathcal{A} = \lbrace (A,D), (A,B), (A,C), (B,E), (B,C), (D,E) \rbrace$$$\begin{pmatrix}1 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & \textbf{1} … text/html 2021-11-12T15:41:53+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.goupill.fr/doku.php?id=nsi:terminales:graphes:dijkstra&rev=1636731713&do=diff Plus court chemin, Algorithme de Dijkstra Pour les besoins de cette partie, considérons un réseau constitué de routeurs, sur lequel on indique les distances entre routeurs. On souhaite trouver le plus court chemin entre deux sommets. Algorithme de Dijkstra text/html 2021-12-16T17:51:12+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.goupill.fr/doku.php?id=nsi:terminales:graphes:implementation&rev=1639677072&do=diff Implémentation graphes Je propose d'utiliser une classe pour implémenter un graphe. Il existe plusieurs possibilités. On pourrait travailler avec des nœuds reliés comme ceux d'un arbre. D'ailleurs un arbre est un graphe particulier. Dans l'exemple qui suit je propose d'utiliser plutôt un objet pour l'arbre dans son ensemble, contenant la totalité des informations surs les sommets et les arêtes. text/html 2021-12-09T19:31:27+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.goupill.fr/doku.php?id=nsi:terminales:graphes:parcours&rev=1639078287&do=diff Parcours d'un graphe On retrouve les notions de parcours en largeur et en profondeur déjà rencontrées avec les arbres. Parcours en largeur Passe par l'utilisation d'une file. Contrairement aux arbres, il peut y avoir des boucles dans les graphes et on risque de parcourir plusieurs fois un même sommet. On marque donc les sommets visités pour ne pas les visiter deux fois.