Obtenez un aperçu de la structure des données graphiques ici...

Ce blog s'adresse aux développeurs qui souhaitent comprendre l'essentiel d'un concept et ne pas tourner autour du pot. Nous comprendrons la structure des données graphiques dans cet article. Commençons.

Que sont les graphiques ?

Les graphiques sont des structures de données non linéaires à 2 composants, à savoir les arêtes et les nœuds.

Un nœud est : -

1. une unité de base du graphique,
2. également connu sous le nom de sommet ou sommets, et
3. peut être étiqueté ou non.

Un bord c'est:-

1. une connexion entre deux nœuds,
2. également connu sous le nom d'arcs, et
3. peut être étiqueté ou non.

Types de graphique : -

1. Graphique nul : Il n'a pas d'arêtes,
2. Graphique Trival : Il n'a qu'un seul nœud,
3. Graphique cyclique : Il contient au moins un cycle,
4. Graphique de cycle : Tous les nœuds sont connectés pour former un cycle,
5. Graphique orienté : Ses arêtes ont une direction,
6. Graphique non orienté : Ses arêtes n'ont aucune direction,
7. Graphique pondéré : Une valeur est attribuée à chaque arête,
8. Graphique connecté : Nous pouvons visiter n'importe quel autre nœud à partir d'un nœud (il n'est pas nécessaire qu'il s'agisse d'une arête unique),
9. Graphique non connecté : Au moins un nœud est déconnecté d'un nœud,
10. Graphique régulier : Chaque sommet a le même nombre de voisins,
11. Graphique complet : Chaque nœud est connecté à un autre nœud par une arête unique,
12. Graphique acyclique dirigé : Un graphe orienté sans cycles,
13. Graphique biparti : Ses nœuds peuvent être divisés en 2 ensembles de telle sorte qu'aucune arête n'existe parmi les ensembles.

Comment stockons-nous les graphiques ?

Il y a 2 façons :

1. Matrice adjacente, et
2. Matrice adjacente

La matrice adjacente est une matrice 2D représentant la structure des données graphiques. Les lignes et les colonnes représentent les nœuds et la valeur dans la matrice représente les arêtes.

Dans l'image ci-dessus, 4 nœuds sont reliés par les bords. Le nœud A est connecté à tous les nœuds et donc la valeur est ajoutée à 1 dans les cellules où A (ligne ou colonne) croise les lignes ou colonnes d'autres nœuds. Le nœud B est uniquement connecté au nœud A, ce qui donne une valeur 1 dans la cellule où le nœud B croise le nœud A et les autres cellules ont une valeur 0.

La complexité temporelle pour ajouter ou supprimer une arête pour la matrice adjacente est O(1). Il peut être utilisé lorsque : -

1. le graphique a le maximum d'arêtes possibles,
2. il n'y a pas de contrainte de mémoire, et
3. le graphique a une structure complexe.

La liste adjacente stocke le graphique à l'aide de plusieurs listes ou tableaux chaînés. Les lignes représentent le nœud (vérifiez l'image ci-dessous) et les valeurs présentes dans les lignes représentent le voisin.

Dans l'image ci-dessus, il y a 5 nœuds. Le nœud A est connecté au nœud B et au nœud D, c'est pourquoi le premier tableau a ces valeurs. De même, le nœud B est connecté au nœud A, au nœud C, au nœud D et au nœud E et le deuxième tableau contient donc ces nœuds dans le deuxième tableau.

La complexité temporelle pour récupérer ou supprimer un bord est O(n) et la complexité temporelle pour ajouter un bord est O(1). La liste adjacente peut être utilisée lorsque : -

1. le nœud a moins d'arêtes,
2. il y a des contraintes de mémoire, et
3. le graphique est moins complexe.

Fig : Comparaison visuelle entre la liste adjacente et la matrice adjacente.

Cas d'utilisation des graphiques

Un exemple populaire de structure de données graphiques est le suivant : dans un terrain de football, chaque joueur peut être considéré comme un nœud et leurs interactions représentent des bords.

Les graphiques sont utilisés dans des scénarios similaires à ceux de l'exemple précédent, tels que : -

1. dans les réseaux sociaux où chacun est un nœud,
2. dans les réseaux informatiques où les PC et les routeurs sont les nœuds,
3. dans le réseau de transport, et ainsi de suite...

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!