Structure des données - Structure des données du graphique
Un graphique est une représentation picturale d'un ensemble d'objets où certaines paires d'objets sont reliées par des liens. Les objets interconnectés sont représentés par des points appelésvertices, et les liens qui relient les sommets sont appelés edges.
Formellement, un graphique est une paire d'ensembles (V, E), où V est l'ensemble des sommets et Eest l'ensemble des arêtes, reliant les paires de sommets. Jetez un œil au graphique suivant -
Dans le graphique ci-dessus,
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Structure des données graphiques
Les graphiques mathématiques peuvent être représentés dans une structure de données. Nous pouvons représenter un graphe en utilisant un tableau de sommets et un tableau à deux dimensions d'arêtes. Avant d'aller plus loin, familiarisons-nous avec quelques termes importants -
Vertex- Chaque nœud du graphe est représenté comme un sommet. Dans l'exemple suivant, le cercle étiqueté représente des sommets. Ainsi, A à G sont des sommets. Nous pouvons les représenter à l'aide d'un tableau comme le montre l'image suivante. Ici, A peut être identifié par l'index 0. B peut être identifié en utilisant l'index 1 et ainsi de suite.
Edge- Edge représente un chemin entre deux sommets ou une ligne entre deux sommets. Dans l'exemple suivant, les lignes de A à B, de B à C, etc. représentent des arêtes. Nous pouvons utiliser un tableau à deux dimensions pour représenter un tableau comme indiqué dans l'image suivante. Ici, AB peut être représenté par 1 à la ligne 0, colonne 1, BC par 1 à la ligne 1, colonne 2 et ainsi de suite, en gardant les autres combinaisons à 0.
Adjacency- Deux nœuds ou sommets sont adjacents s'ils sont connectés l'un à l'autre via une arête. Dans l'exemple suivant, B est adjacent à A, C est adjacent à B, et ainsi de suite.
Path- Path représente une séquence d'arêtes entre les deux sommets. Dans l'exemple suivant, ABCD représente un chemin de A à D.
Opérations de base
Voici les opérations principales de base d'un graphique -
Add Vertex - Ajoute un sommet au graphique.
Add Edge - Ajoute une arête entre les deux sommets du graphe.
Display Vertex - Affiche un sommet du graphique.
Pour en savoir plus sur Graph, veuillez lire le didacticiel sur la théorie des graphes . Nous apprendrons à parcourir un graphe dans les prochains chapitres.