Les graphes sont des structures de données fondamentales permettant de modéliser des réseaux (Internet, réseaux sociaux, transports) ou des relations complexes.
Il existe deux méthodes principales pour coder un graphe en Python :
Un tableau 2D (liste de listes) où M[i][j] = 1 si un lien existe entre i et j.
Un dictionnaire où chaque clé est un sommet et la valeur est la liste de ses voisins.
graphe = { 'A': ['B', 'C'], 'B': ['A', 'D'], ... }
Pour explorer un graphe, on utilise deux algorithmes classiques :
Explore étage par étage. Utilise une FILE (FIFO).
Parcours en Profondeur (DFS - Depth First Search)Explore une branche jusqu'au bout avant de revenir. Utilise une PILE (LIFO) ou la récursivité.
Voici un graphe généré aléatoirement. Répondez aux 10 questions d'analyse ci-dessous.