37. Représentation des Graphes
La manière dont nous stockons les données du graphe a un impact significatif sur l'efficacité des algorithmes qui s'y exécutent.
1. Matrice d'Adjacence (Adjacency Matrix)
- Concept : Un tableau 2D (matrice) de taille V x V, où V est le nombre de sommets.
- Stockage :
Matrix[i][j]stocke un 1 (ou le poids) s'il existe une arête du sommetiau sommetj, et 0 (ou l'infini) sinon. - Avantages : Vérification rapide d'une arête entre deux nœuds spécifiques (O(1)).
- Inconvénients : Gaspille beaucoup d'espace, en particulier pour les Graphes Rares (Sparse Graphs) (graphes avec peu d'arêtes). Complexité spatiale : O(V²).
2. Liste d'Adjacence (Adjacency List)
- Concept : Un tableau ou un Hash Map où chaque index/clé correspond à un sommet. La valeur stockée à cet index est une liste de ses voisins.
- Avantages : Efficace en espace, surtout pour les graphes rares. Complexité spatiale : O(V + E) (Sommets + Arêtes).
- Inconvénients : La vérification de l'existence d'une arête entre deux nœuds nécessite de parcourir la liste des voisins (O(Degré du sommet)).
Règle générale : Les Listes d'Adjacence sont généralement préférées pour la plupart des algorithmes du monde réel, sauf si le graphe est extrêmement dense.