Un liste de contiguïté est une structure de données utilisée pour représenter un graphe dans lequel chaque nœud du graphe stocke une liste de ses sommets voisins.

Représentation graphique du graphique dirigé vers la liste de contiguïté

Caractéristiques de la liste de contiguïté :

• La taille de la matrice est déterminée par le nombre de nœuds du réseau.
• Le nombre d’arêtes du graphique est facilement calculé.
• La liste de contiguïté est un tableau irrégulier .

Comment construire une liste de contiguïté ?

Il est très facile et simple de construire une liste de contiguïté pour un graphique. Vous devez suivre certaines étapes ci-dessous :

• Créer un tableau de listes chaînées de taille N , où N est le nombre de sommets du graphe.
• Créez une liste chaînée de sommets adjacents pour chaque sommet du graphique.
• Pour chaque bord (tu, v) dans le graphique, ajoutez dans à la liste chaînée de dans , et ajouter dans à la liste chaînée de dans si le graphique n'est pas orienté sinon ajouter dans à la liste des dans s'il est dirigé de dans à dans . (Dans le cas de graphiques pondérés, stockez le poids avec les connexions).

Applications de la liste de contiguïté :

• L'algorithme de Dijkstra , Recherche en largeur d'abord , et Recherche en profondeur d'abord utiliser des listes de contiguïté pour représenter des graphiques.
• Traitement d'image : Les listes de contiguïté peuvent être utilisées pour représenter les relations de contiguïté entre les pixels d'une image.
• Développement de jeu : Ces listes peuvent être utilisées pour stocker des informations sur les connexions entre différentes zones ou niveaux. Les développeurs de jeux utilisent des graphiques pour représenter les cartes ou les niveaux du jeu.

Avantages de l'utilisation d'une liste de contiguïté :

• Une liste de contiguïté est simple et facile à comprendre.
• L'ajout ou la suppression d'arêtes d'un graphique est simple et rapide.

Inconvénients de l'utilisation d'une liste de contiguïté :

• Dans les listes de contiguïté, l'accès aux bords peut prendre plus de temps que la matrice de contiguïté.
• Elle nécessite plus de mémoire que la matrice de contiguïté pour les graphes denses.

Que pouvez-vous lire d'autre ?

• Matrice d’adjacence : signification et définition dans DSA
• Ajouter et supprimer un bord dans la représentation de liste de contiguïté d'un graphique
• Convertir la matrice de contiguïté en représentation de liste de contiguïté du graphique
• Convertir la liste de contiguïté en représentation matricielle de contiguïté d'un graphique
• Comparaison entre la liste de contiguïté et la représentation matricielle de contiguïté du graphique