Numérique et sciences informatiques (spécialité) · Terminale · Structures de données

Graphes : représentations

• Un graphe est un ensemble de sommets reliés par des arêtes (non orienté) ou des arcs (orienté) ; son dessin n'est pas unique .
• La matrice d'adjacence est un tableau carré de 0 et de 1 : la case (i, j) vaut 1 s'il existe une liaison de i vers j. Elle est symétrique si le graphe est non orienté.
• La liste d'adjacence (ou le dictionnaire de listes) range, pour chaque sommet, la liste de ses voisins .
• Matrice : test d'une arête immédiat mais mémoire en n². Listes : mémoire proportionnelle aux sommets + arêtes, idéale pour les graphes peu denses.