À retenir
- Composé de sommets (les objets) et d'arêtes (les liens).
- Peut être orienté (les liens ont une flèche de direction) ou non orienté.
- Permet de modéliser n'importe quel système interconnecté.
Un graphe est une structure de données qui permet de représenter des relations complexes entre des objets. Imaginez un réseau social : chaque utilisateur est un point (appelé sommet ou nœud) et chaque lien d'amitié est un trait (appelé arête) reliant deux points.
Étymologie
Le mot provient du grec ancien graphein, qui signifie « écrire » ou « dessiner ». En informatique, il est hérité de la théorie des graphes, une branche des mathématiques formalisée au XVIIIe siècle pour résoudre des problèmes de chemins et de réseaux.
Exemples d'usage
- Un GPS : les intersections sont les sommets et les routes sont les arêtes.
- Le Web : chaque page est un sommet et chaque lien hypertexte est une arête orientée.
- Un réseau électrique : les centrales et les transformateurs sont reliés par des lignes de haute tension.
Cas d'usage
On utilise les graphes pour calculer des itinéraires (algorithme de Dijkstra), analyser des réseaux sociaux, gérer des recommandations d'achat (« les clients ayant acheté ceci ont aussi aimé cela ») ou encore pour structurer des bases de données de type NoSQL (orientées graphe).
Bonnes pratiques
Le choix de la représentation technique est crucial : utilisez une matrice d'adjacence (un tableau à deux dimensions) si le graphe est très dense, ou une liste d'adjacence (une liste de voisins pour chaque nœud) si le graphe comporte peu de liens, afin d'économiser de la mémoire.
Synonymes
Antonymes
Conseil
Pour bien débuter, essayez de dessiner vos structures sur papier. Si vous devez coder un graphe, commencez par comprendre la différence entre un parcours en largeur (BFS) pour trouver le chemin le plus court et un parcours en profondeur (DFS) pour explorer toutes les possibilités.
Questions fréquentes
Quelle est la différence entre un arbre et un graphe ?
Un arbre est un type particulier de graphe qui est connecté et ne possède aucun cycle (on ne peut pas revenir à son point de départ sans faire demi-tour).
C'est quoi un graphe pondéré ?
C'est un graphe où chaque arête possède une valeur (un poids), comme la distance en kilomètres entre deux villes sur une carte.