Introduction au graphe dans la structure des données
Les graphiques sont des structures de données non linéaires comprenant un ensemble fini de nœuds et d'arêtes. Les nœuds sont les éléments et les bords sont des paires ordonnées de connexions entre les nœuds.
Remarquez le mot non linéaire. Une structure de données non linéaire est une structure où les éléments ne sont pas disposés dans un ordre séquentiel. Par exemple, un tableau est une structure de données linéaire car les éléments sont disposés les uns après les autres. Vous pouvez parcourir tous les éléments d'un tableau en une seule fois. Ce n'est pas le cas avec les structures de données non linéaires. Les éléments d'une structure de données non linéaire sont organisés en plusieurs niveaux, suivant souvent un modèle hiérarchique. Les graphiques sont non linéaires.
Le mot suivant auquel prêter attention est fini. Nous définissons le graphe comme ayant un nombre fini et dénombrable de nœuds. C'est un terme plutôt inacceptable. Essentiellement, un graphe peut avoir un nombre infini de nœuds et être néanmoins fini. Par exemple, un arbre généalogique remontant à Adam et Eve. Il s'agit d'un graphe relativement infini mais toujours dénombrable et est donc considéré comme fini.
Exemple du monde réel
Facebook est le meilleur exemple de graphiques dans le monde réel. Chaque personne sur Facebook est un nœud et est connectée via des bords. A est un ami de B. B est un ami de C et ainsi de suite.
Terminologies
Voici les terminologies du graphique dans la structure de données mentionnées ci-dessous
1. Représentation graphique: Généralement, un graphique est représenté comme une paire d'ensembles (V, E). V est l'ensemble des sommets ou nœuds. E est l'ensemble des bords. Dans l'exemple ci-dessus,
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. Nœud ou sommet: les éléments d'un graphique sont connectés par des bords.
3. Bords: Un chemin ou une ligne entre deux sommets dans un graphique.
4. Noeuds adjacents: deux noeuds sont appelés adjacents s'ils sont connectés via une arête. Dans l'exemple ci-dessus, le nœud A est adjacent aux nœuds B, C et D, mais pas au nœud E.
5. Chemin: Le chemin est une séquence d'arêtes entre deux nœuds. Il s'agit essentiellement d'une traversée commençant à un nœud et se terminant à un autre. Dans l'exemple ci-dessus, il existe plusieurs chemins du nœud A au nœud E.
Chemin (A, E) = (AB, BE)
OU
Chemin (A, E) = (AC, CD, DE)
OU
Chemin (A, E) = (AD, DE)
6. Graphique non orienté : Un graphique non orienté est un graphique où les bords ne spécifient pas une direction particulière. Les bords sont bidirectionnels.
Exemple
Ainsi, dans cet exemple, le bord AC peut être traversé de A à C et de C à A. Semblable à tous les bords. Un chemin allant du nœud B au nœud C serait soit (BA, AC) ou (BD, DC).
7. Graphique dirigé: Un graphique dirigé est celui où les bords peuvent être traversés dans une direction spécifiée uniquement.
Exemple
Ainsi, dans le même exemple, maintenant les bords sont directionnels. Vous ne pouvez traverser l'arête que dans sa direction. Il n'y a aucun chemin du nœud B au nœud C maintenant.
8. Graphique pondéré: Un graphique pondéré est celui où les bords sont associés à un poids. Il s'agit généralement du coût de traversée du bord.
Exemple
Ainsi, dans le même exemple, maintenant les bords ont un certain poids qui leur est associé. Il existe deux chemins possibles entre le nœud A et le nœud E.
Path1 = (AB, BD, DE), Weight1 = 3 + 2 + 5 = 10
Path2 = (AC, CD, DE), Weight2 = 1 + 3 + 5 = 9
Clairement, on préférerait Path2 si le but est d'atteindre le nœud E à partir du nœud A avec un coût minimum.
Opérations de base sur le graphique
Voici les opérations de base de la mention graphique ci-dessous
1. Ajouter / supprimer un sommet
Il s'agit de l'opération la plus simple du graphique. Vous ajoutez simplement un sommet à un graphique. Il n'a pas besoin d'être connecté à un autre sommet par une arête. Lors de la suppression d'un sommet, vous devez supprimer toutes les arêtes provenant et se terminant au sommet supprimé.
2. Ajouter / supprimer un bord
Cette opération ajoute ou supprime une arête entre deux sommets. Lorsque toutes les arêtes provenant et se terminant à un sommet sont supprimées, le sommet devient un sommet isolé.
3. Recherche en largeur d'abord (BFS)
Il s'agit d'une opération de traversée dans le graphique. BFS parcourt horizontalement le graphique. Cela signifie qu'il traverse tous les nœuds à un seul niveau avant de passer au niveau suivant.
L'algorithme BFS commence en haut du premier nœud du graphe, puis y traverse tous les nœuds adjacents. Une fois tous les nœuds adjacents traversés, l'algorithme répète la même procédure pour les nœuds enfants.
Exemple
Traverser le graphique ci-dessus à la manière de BFS résulterait de A -> B -> C -> D -> E -> F -> G. L'algorithme commence à partir du nœud A et traverse tous ses nœuds adjacents B, C et D. Il marque tous les quatre nœuds comme visités. Une fois que tous les nœuds adjacents de A sont traversés, l'algorithme se déplace vers le premier nœud adjacent de A et répète la même procédure. Dans ce cas, le nœud est B et les nœuds adjacents à B sont E et F. Ensuite, les nœuds adjacents à C sont traversés. Une fois tous les nœuds visités, l'opération se termine.
4. Recherche en profondeur en premier (DFS)
Depth First Search ou DFS parcourt le graphique verticalement. Il commence par le nœud racine ou le premier nœud du graphe et traverse tous les nœuds enfants avant de se déplacer vers les nœuds adjacents.
Exemple
Traverser le graphique ci-dessus à la manière de BFS résulterait de A -> B -> E -> F -> C -> G -> D. L'algorithme commence à partir du nœud A et traverse tous ses nœuds enfants. Dès qu'il rencontre B, il semble qu'il ait d'autres nœuds enfants. Ainsi, les nœuds enfants de B sont traversés avant de passer au nœud enfant suivant de A.
Implémentations réelles des graphiques
- Conception de circuits électriques pour la transmission de puissance.
- Conception d'un réseau d'ordinateurs interconnectés.
- Étude de la structure moléculaire, chimique et cellulaire de toute substance, par exemple l'ADN humain.
- Conception d'itinéraires de transport entre les villes et les lieux d'une ville.
Conclusion - Graphique dans la structure des données
Les graphiques sont un concept très utile dans les structures de données. Il a des implémentations pratiques dans presque tous les domaines. Il est très important de comprendre les bases de la théorie des graphes, de développer une compréhension des algorithmes de la structure des graphes.
Cet article n'était qu'une introduction aux graphiques. Ce n'est qu'un tremplin. Il est recommandé d'approfondir le sujet de la théorie des graphes.
Articles recommandés
Ceci est un guide du graphique dans la structure des données. Ici, nous discutons des terminologies et des opérations de base du graphe dans la structure des données. Vous pouvez également consulter l'article suivant pour en savoir plus -
- Questions d'entretiens chez Data Structure
- Modèle de données dans Cassandra
- Qu'est-ce que Data Mart?
- Qu'est-ce qu'un Data Scientist?