Quand la hiérarchie ne suffit plus
Un graphe représente des relations. Un nœud peut être relié à plusieurs autres, sans parent unique et sans ordre linéaire imposé.
Un réseau social, des villes reliées par des routes, des pages web ou des tâches qui dépendent les unes des autres ne forment pas forcément une hiérarchie. Plusieurs chemins peuvent relier les mêmes entités et un lien peut revenir vers une zone déjà rencontrée.
Liste
- Chaque élément mène naturellement au suivant.
- La position ou l'ordre porte le sens.
Arbre
- Chaque nœud s'inscrit dans une hiérarchie.
- Un chemin descend depuis une racine.
Graphe
- Les relations peuvent se croiser et revenir.
- Une entité peut avoir plusieurs voisins sans parent unique.
| Terme | Question concrète | Exemple |
|---|---|---|
| Nœud | Quelle entité est représentée ? | Une ville |
| Arête | Quel lien unit deux entités ? | Une route |
| Voisin | Quel nœud est relié directement ? | Lausanne est voisine de Genève |
| Chemin | Quelle suite d'arêtes relie le départ à l'arrivée ? | Genève, Lausanne, Fribourg |
| Cycle | Peut-on suivre des liens et revenir au départ ? | Une boucle de routes |
| Composante | Quel groupe reste séparé du reste ? | Une île sans liaison |
Arbre et liste : des graphes très contraints
Une liste chaînée impose presque un seul chemin. Un arbre impose une hiérarchie sans retour vers un parent déjà traversé. Le graphe général retire ces contraintes et vous oblige à décrire précisément la nature des liens.
Quatre questions pour qualifier un graphe
Avant de choisir une représentation, qualifiez le problème. Quatre questions courtes suffisent pour le niveau attendu ici.
Le sens compte-t-il ?
Si A vers B ne signifie pas automatiquement B vers A, le graphe est orienté. Une arête dans chaque sens représente alors deux informations distinctes.Le lien porte-t-il un coût ?
Une distance, une durée ou un prix rend le graphe pondéré. Le poids appartient à l'arête.Tout est-il relié ?
Si chaque nœud appartient au même ensemble de relations, le graphe est connexe. Sinon, il possède plusieurs composantes. Pour un graphe orienté, répondez en ignorant le sens des flèches : exiger des trajets orientés dans les deux sens (la connexité forte) sort du niveau attendu.Peut-on revenir au départ ?
Si une suite d'arêtes forme un chemin fermé, le graphe est cyclique. Cette question ne dit rien, à elle seule, sur la connexité.
| Propriété | Oui | Non | Ce que cela change |
|---|---|---|---|
| Sens | graphe orienté | Non orienté | Une flèche peut exister sans son retour. |
| Coût | Pondéré | Non pondéré | L'arête stocke ou non une mesure. |
| Ensemble | Connexe | Non connexe | Des morceaux peuvent rester isolés. |
| Retour | Cyclique | Acyclique | Un chemin fermé existe ou non. |
Le code minimal : un nœud et ses liens
La représentation Java la plus directe place sur chaque nœud la liste de ses liens sortants. Ajouter A vers B ne crée pas automatiquement B vers A.
Quand le lien porte sa propre donnée, remplacez la référence directe par un objet arête. Ici, weight peut représenter une distance, un coût ou une durée.
Restez minimal
Pour cette remédiation, ces deux petites classes suffisent. Vous n'avez pas besoin d'une classe Graph complète, de génériques ou d'une API industrielle pour expliquer le modèle.
Trois représentations du même graphe
Les trois représentations suivantes décrivent exactement les mêmes quatre nœuds et les mêmes quatre arêtes. Seule leur organisation en mémoire change.
Liste d'arêtes
Stockez chaque relation comme un tuple source, destination, poids. C'est compact à écrire et simple à charger depuis un fichier.Liste d'adjacence
Associez chaque nœud à ses voisins sortants. Les voisins de A sont regroupés au même endroit.Matrice d'adjacence
Réservez une ligne et une colonne par nœud. La case ligne A, colonne B dit immédiatement si A pointe vers B et porte son poids.
Même graphe, réponses différentes
Une représentation n'est pas « plus vraie » qu'une autre. Elle rend certaines questions faciles et en fait payer d'autres en mémoire ou en comparaisons.
Choisir selon l'opération utile
| Représentation | Très pratique pour | Compromis |
|---|---|---|
| Liste d'arêtes | Écrire, sérialiser ou relire toutes les relations. | Trouver les voisins d'un nœud demande de rescanner les arêtes. |
| Liste d'adjacence | Lire directement les voisins d'un nœud. | Tester un lien précis demande de parcourir sa liste locale. |
| Matrice d'adjacence | Tester immédiatement si A est relié à B. | Elle réserve une case pour chaque paire, même sans arête. |
Graphe peu connecté
- La plupart des paires de nœuds n'ont aucun lien.
- La liste d'adjacence ne stocke que les relations présentes.
Graphe très connecté
- Beaucoup de paires possèdent une arête.
- La place réservée par une matrice est moins gaspillée.
Réponse d'examen
- Nommez d'abord l'opération dominante.
- Choisissez ensuite la représentation qui la sert.
- Annoncez enfin ce que ce choix coûte ailleurs.
Ce qu'il faut savoir, et pas davantage
Le niveau attendu s'arrête à la modélisation, aux quatre propriétés, au code minimal et au choix entre les trois représentations.
Aucun algorithme à apprendre ici
Vous devez pouvoir dessiner un petit graphe, traduire ce dessin en données et justifier une représentation. Cette leçon ne demande pas d'écrire une méthode pour explorer le réseau, calculer un chemin ou détecter un cycle.
Les pièges qui restent évaluables
- A vers B n'implique pas B vers A dans un graphe orienté.
- Une arête porte le poids, pas le nœud d'arrivée.
- Connexe et cyclique répondent à deux questions différentes.
- Une matrice stocke aussi toutes les absences de lien.
Vérifiez vos réflexes
Vérifiez vos réflexes
Une réponse par question. La correction apparaît tout de suite.