Comment fonctionnent les graphes en NSI et à quoi servent-ils
Les graphes sont une structure de données essentielle en terminale NSI qui modélise des relations entre éléments. Un graphe est composé de sommets (ou nœuds) reliés par des arêtes (graphe non orienté) ou des arcs (graphe orienté). Un graphe peut être pondéré (chaque arête a un poids/coût). Les représentations informatiques sont : la matrice d'adjacence (tableau 2D où M[i][j] = 1 si une arête relie i à j) et la liste d'adjacence (dictionnaire où chaque sommet est associé à la liste de ses voisins). Les algorithmes fondamentaux sont le parcours en profondeur (DFS, utilisant une pile ou la récursivité) et le parcours en largeur (BFS, utilisant une file). L'algorithme de Dijkstra trouve le plus court chemin dans un graphe pondéré. Les applications des graphes sont omniprésentes : réseaux sociaux (relations d'amitié), GPS (plus court chemin), Internet (routage), planification de tâches (ordonnancement). Au bac, vous devez savoir représenter un graphe, le parcourir et appliquer les algorithmes classiques. Sur NSI-Lycée, les graphes sont illustrés avec des visualisations interactives qui montrent le déroulement pas à pas des algorithmes. Consultez revisemaths.fr pour la théorie des graphes en mathématiques, et allogeopolitique.fr pour les applications géopolitiques des réseaux.
