Liste de contiguïté et représentation matricielle du graphique
Équipe éditoriale
⚡ Résumé intelligent
Les listes d'adjacence et les matrices d'adjacence permettent de stocker les sommets et les arêtes en mémoire, ce qui permet aux algorithmes de parcourir les réseaux. Une liste d'adjacence utilise une liste chaînée par sommet, tandis qu'une matrice d'adjacence utilise une grille carrée bidimensionnelle.
Même s'ils semblent différents, tous types de graphiques peut être représenté de manière similaire. Il existe généralement deux types de représentation graphique :
- Matrice d'adjacence
- Liste de contiguïté
Liste de contiguïté
Une liste d'adjacence est composée de listes chaînées. Chaque sommet est considéré comme un indice de tableau, et chaque élément représente une liste chaînée. Ces listes chaînées contiennent les sommets qui partagent une arête avec le sommet d'indice.
Voici un exemple de liste d'adjacence :
Soit un graphe comportant V sommets et E arêtes. La complexité spatiale de la liste d'adjacence est O(V + E), qui évolue en fonction du nombre d'arêtes réelles plutôt que de chaque paire de sommets possibles.
La complexité spatiale dans le pire des cas devient O(V²) si le graphe donné est un graphe complet, puisque chaque sommet est alors connecté à tous les autres sommets.
Matrice d'adjacence
Une matrice d'adjacence est composée d'un tableau 2D. Pour un graphe à V sommets, la taille de la matrice sera de V × V.
nos élèves matrix[i][j] = 5Cela signifie qu'il existe une arête entre le nœud i et le nœud j dont le poids est de 5.
Examinons le graphe suivant et sa matrice d'adjacence :
Nous avons construit le tableau 2D en utilisant ces étapes :
Étape 1) Le sommet A est directement relié à B par une arête de poids 5. Par conséquent, la case située à l'intersection de la ligne A et de la colonne B sera remplie avec la valeur 5. Les autres cases de la ligne A seront remplies avec la valeur 0.
Étape 2) Le sommet B possède une arête directe avec C, et le poids de cette arête est de 4. Par conséquent, la cellule située à l'intersection de la ligne B et de la colonne C sera remplie avec la valeur 4. Les cellules restantes de la ligne B seront remplies avec la valeur zéro, puisque B ne possède aucune arête sortante vers un autre nœud.
Étape 3) Le sommet C n'est relié directement à aucun autre sommet. Par conséquent, la ligne C sera remplie de zéros.
Étape 4) Le sommet D possède une arête orientée avec A et C.
- La cellule située à l'intersection de la ligne D et de la colonne A aura la valeur 7. La cellule située à l'intersection de la ligne D et de la colonne C aura la valeur 2.
- Le reste des cellules de la ligne D sera rempli de zéros.
Étape 5) Le sommet E est relié par une arête orientée à B et D. La cellule située à l'intersection de la ligne E et de la colonne B aura la valeur 6. La cellule située à l'intersection de la ligne E et de la colonne D aura la valeur 3. Les autres cellules de la ligne E seront remplies de zéros.
Voici quelques points à noter :
- Le graphe ne comporte pas de boucles lorsque la diagonale principale de la matrice d'adjacence est égale à 0.
- Un graphe est orienté si les cellules aux coordonnées (a, b) et (b, a) ne contiennent pas la même valeur. Sinon, il est non orienté.
- Le graphique est un graphique pondéré si la valeur de n'importe quelle cellule est supérieure à 1.
Le principal problème de la matrice d'adjacence est qu'elle nécessite un espace mémoire au carré. Même les arêtes inexistantes occupent des cellules en mémoire.
Par exemple, si nous avons un graphe avec 100 nœuds, alors 10 000 cellules sont nécessaires pour le stocker. RAMAvec un nombre réduit d'arêtes dans le graphe, allouer une mémoire aussi importante peut s'avérer inutile. La complexité spatiale, calculée à l'aide de la matrice d'adjacence, est donc de : O(N²), où N est le nombre de nœuds dans le graphe.
Liste d'adjacence vs matrice d'adjacence
Avant de choisir une représentation, il est utile de comparer les deux modèles côte à côte sur les opérations qui dominent les charges de travail graphiques réelles :
| Opération | Matrice d'adjacence | Liste de contiguïté |
|---|---|---|
| Complexité spatiale | O(V²) | O(V + E) |
| Ajouter un sommet | O(V²) | O (1) |
| Ajouter un bord | O (1) | O (1) |
| Enlever un bord | O (1) | O(E) |
| Vérifier si l'arête (i, j) existe | O (1) | O(degré de i) |
| Parcourir les voisins de i | O (V) | O(degré de i) |
| Meilleur pour | Graphes denses, requêtes fréquentes sur les arêtes | Graphes clairsemés, tâches nécessitant de nombreux parcours |
En résumé, la matrice d'adjacence l'emporte sur les recherches d'arêtes en temps constant, tandis que la liste d'adjacence l'emporte sur la mémoire et l'itération des voisins, ce qui explique pourquoi des algorithmes tels que BFS, DFS et Dijkstra sont généralement associés à des listes d'adjacence.
Avantages et inconvénients de la représentation graphique
Chaque représentation présente ses propres avantages et inconvénients. Connaître les forces et les faiblesses des deux modèles vous aide à choisir celui qui convient le mieux au problème que vous cherchez à résoudre.
Avantages de la matrice d'adjacence :
- Requêtes d'existence d'arêtes en temps constant O(1) entre n'importe quelle paire de sommets.
- L'indexation fixe facilite la mise en œuvre d'algorithmes matriciels tels que Floyd-Warshall et la fermeture transitive.
- Les bords pondérés s'intègrent naturellement dans une seule cellule de la matrice.
Inconvénients de la matrice d'adjacence :
- Gaspille O(V²) de mémoire lorsque le graphe est clairsemé.
- L'ajout d'un nouveau sommet nécessite le redimensionnement de la matrice entière.
- L'itération sur les voisins d'un seul sommet prend O(V) même lorsque le sommet n'a que quelques arêtes.
Avantages de la liste d'adjacence :
- Utilise seulement O(V + E) mémoire, ce qui est proche du nombre réel d'arêtes dans les graphes creux.
- L'ajout d'un nouveau sommet ou d'une nouvelle arête est O(1).
- Les algorithmes de parcours tels que BFS et DFS itèrent les voisins en O(degré), donnant un temps d'exécution global de O(V + E).
Inconvénients de la liste d'adjacence :
- Vérifier si une arête spécifique existe prend un temps O(degré) au lieu de O(1).
- La localité du cache est plus faible car les listes chaînées sont dispersées dans la mémoire.
- Les arêtes pondérées nécessitent un champ associé ou une liste de paires, ce qui complexifie légèrement la structure des données.
Quand utiliser une liste d'adjacence plutôt qu'une matrice d'adjacence ?
Le choix de la représentation dépend de la densité du graphe et des opérations les plus fréquentes. Utilisez ce guide rapide pour choisir la structure appropriée :
- Privilégier la matrice d'adjacence lorsque le graphe est dense (E est proche de V²), lorsque les arêtes changent rarement et lorsque votre algorithme demande plusieurs fois « existe-t-il une arête entre i et j ? ».
- Préférez la liste d'adjacence lorsque le graphe est creux (E est beaucoup plus petit que V²), lorsque l'ensemble des sommets ou des arêtes s'accroît pendant l'exécution, et lorsque vous parcourez le graphe avec BFS, DFS ou L'algorithme de Dijkstra pour trouver le plus court chemin.
- Je préfère un modèle mixte (liste d'adjacence plus un ensemble de hachage d'arêtes) lorsque vous avez besoin à la fois d'une itération rapide des voisins et de requêtes d'arêtes O(1), au prix d'une mémoire supplémentaire.
Les bibliothèques graphiques modernes telles que NetworkX et igraph utilisent par défaut des listes d'adjacence car la plupart des graphes du monde réel (réseaux sociaux, cartes routières, pages Web, dépendances de packages) sont clairsemés et nécessitent de nombreux parcours.
