Dans ce didacticiel, vous apprendrez ce qu'est une structure de données graphique. Vous trouverez également des représentations d'un graphique.
Une structure de données de graphique est un ensemble de nœuds contenant des données et connectés à d'autres nœuds.
Essayons de comprendre cela à travers un exemple. Sur Facebook, tout est un nœud. Cela inclut l'utilisateur, la photo, l'album, l'événement, le groupe, la page, le commentaire, l'histoire, la vidéo, le lien, la note… tout ce qui contient des données est un nœud.
Chaque relation est un bord d'un nœud à un autre. Que vous postez une photo, rejoignez un groupe, comme une page, etc., un nouvel avantage est créé pour cette relation.
Exemple de structure de données graphique
Tout Facebook est alors une collection de ces nœuds et bords. En effet, Facebook utilise une structure de données graphique pour stocker ses données.
Plus précisément, un graphe est une structure de données (V, E) qui se compose de
- Une collection de sommets V
- Une collection d'arêtes E, représentée par des paires ordonnées de sommets (u, v)
Sommets et arêtes
Dans le graphique,
V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)
Terminologie des graphes
- Adjacence : un sommet est dit adjacent à un autre sommet s'il y a une arête qui les relie. Les sommets 2 et 3 ne sont pas adjacents car il n'y a pas d'arête entre eux.
- Chemin : Une séquence d'arêtes qui vous permet de passer du sommet A au sommet B est appelée un chemin. 0-1, 1-2 et 0-2 sont des chemins du sommet 0 au sommet 2.
- Graphe dirigé : Un graphe dans lequel une arête (u, v) ne signifie pas nécessairement qu'il existe également une arête (v, u). Les arêtes d'un tel graphique sont représentées par des flèches pour indiquer la direction de l'arête.
Représentation graphique
Les graphiques sont généralement représentés de deux manières:
1. Matrice d'adjacence
Une matrice de contiguïté est un tableau 2D de sommets V x V. Chaque ligne et colonne représente un sommet.
Si la valeur d'un élément a(i)(j)est 1, cela signifie qu'il y a une arête reliant le sommet i et le sommet j.
La matrice de contiguïté pour le graphique que nous avons créé ci-dessus est
Matrice de contiguïté graphique
Puisqu'il s'agit d'un graphe non orienté, pour l'arête (0,2), nous devons également marquer l'arête (2,0); rendre la matrice d'adjacence symétrique par rapport à la diagonale.
La recherche d'arête (vérifier si une arête existe entre le sommet A et le sommet B) est extrêmement rapide dans la représentation de matrice d'adjacence, mais nous devons réserver de l'espace pour chaque lien possible entre tous les sommets (V x V), donc cela nécessite plus d'espace.
2. Liste de proximité
Une liste de contiguïté représente un graphique sous la forme d'un tableau de listes liées.
L'index du tableau représente un sommet et chaque élément de sa liste chaînée représente les autres sommets qui forment une arête avec le sommet.
La liste de contiguïté pour le graphique que nous avons fait dans le premier exemple est la suivante:
Représentation de la liste de contiguïté
Une liste de contiguïté est efficace en termes de stockage car il suffit de stocker les valeurs des arêtes. Pour un graphique avec des millions de sommets, cela peut signifier beaucoup d'espace économisé.
Opérations graphiques
Les opérations graphiques les plus courantes sont:
- Vérifiez si l'élément est présent dans le graphique
- Traversée graphique
- Ajouter des éléments (sommet, arêtes) au graphique
- Trouver le chemin d'un sommet à un autre
