Résumé
Un graphe est un ensemble de sommets reliés par des arêtes (non orienté) ou des arcs (orienté). Par exemple, un réseau social est un graphe non orienté où les sommets sont les utilisateurs et les arêtes les amitiés. Un plan de métro peut être modélisé par un graphe pondéré où les poids représentent les temps de trajet. On représente un graphe de deux manières : la matrice d'adjacence (tableau 2D de booléens ou entiers) ou les listes d'adjacence (dictionnaire associant à chaque sommet la liste de ses voisins). La matrice d'adjacence convient aux graphes denses, les listes d'adjacence aux graphes creux. Les parcours permettent de visiter tous les sommets accessibles depuis un sommet de départ.