Graphes : matrice d'adjacence et liste d'adjacence en Terminale
Graphes : matrice d'adjacence et liste d'adjacence, c'est une notion de nsi du chapitre « Structures de données (listes, piles, files, arbres, graphes) », au programme de Terminale. Voici le cours, un exemple et de quoi t'entraîner.
Graphes : matrice d'adjacence et liste d'adjacence : le cours
Un graphe est composé de nœuds (sommets) reliés par des arêtes (graphe non orienté) ou des arcs (graphe orienté). On peut le représenter par une matrice d'adjacence (tableau 2D) ou une liste d'adjacence (dictionnaire).
Exemple
Un réseau social : chaque personne est un nœud, une amitié est une arête. La matrice dit si deux personnes sont amies (1 oui, 0 non), la liste d'adjacence énumère les amis de chaque personne.
À retenir
Matrice d'adjacence : accès rapide O(1) mais espace O(n²). Liste d'adjacence : espace O(n+m) où m est le nombre d'arêtes, plus efficace pour graphes creux.
S'entraîner sur graphes : matrice d'adjacence et liste d'adjacence
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
On considère un ABR contenant les valeurs 50, 30, 70, 20, 40, 60, 80. Dessinez l'arbre puis donnez le parcours infixe. Quel est l'intérêt du parcours infixe sur un ABR ?
Corrige cet exercice avec le tuteur →Exercice 2
Représentez le graphe suivant par (1) une matrice d'adjacence, (2) une liste d'adjacence. Sommets : A, B, C, D Arêtes : A-B, A-C, B-C, B-D, C-D Le graphe est-il orienté ou non orienté ? Quel mode de représentation est le plus efficace ici ?
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Structures de données (listes, piles, files, arbres, graphes) (NSI Terminale).