Structures de données
📊 Chapitre : Graphes
1️⃣ Graphes : structures relationnelles
Un graphe est une structure de données permettant de représenter des relations entre des objets.
- Les objets sont appelés sommets.
- Les relations entre ces objets sont appelées arêtes ou arcs.
- Un graphe modélise une situation relationnelle : réseau social, carte routière, réseau informatique, etc.
Contrairement aux arbres (structures hiérarchiques), les graphes représentent des relations plus générales.
2️⃣ Sommets, arêtes et arcs
- Un sommet représente une entité.
- Une arête relie deux sommets dans un graphe non orienté.
- Un arc relie deux sommets avec un sens dans un graphe orienté.
- Un graphe est non orienté si les relations sont bidirectionnelles.
- Un graphe est orienté si les relations ont un sens.
3️⃣ Exemple de graphe non orienté
Considérons le graphe suivant :
- Sommets : A, B, C, D, E
- Arêtes : (A,B), (B,C), (C,E), (D,E), (B,D)
- On observe la présence d’un cycle dans ce graphe : B → C → E → D → B.
4️⃣ Modéliser une situation avec un graphe
- Dans un réseau social : les sommets représentent des personnes.
- Les arêtes représentent des relations d’amitié.
- Dans un réseau routier : les sommets sont des villes.
- Les arêtes représentent des routes.
Un graphe permet donc de représenter formellement une situation réelle.
5️⃣ Représentations d’un graphe
Matrice d’adjacence
Une matrice d’adjacence est un tableau à deux dimensions indiquant la présence ou l’absence d’une arête entre deux sommets.
- Si le graphe possède n sommets, la matrice est de taille n × n.
- La valeur 1 indique la présence d’une arête.
- La valeur 0 indique l’absence d’arête.
Exemple pour le graphe précédent :
- A B C D E
A 0 1 0 0 0
B 1 0 1 1 0
C 0 1 0 0 1
D 0 1 0 0 1
E 0 0 1 1 0
Liste de successeurs
La liste de successeurs associe à chaque sommet la liste des sommets qui lui sont reliés.
A : B
B : A, C, D
C : B, E
D : B, E
E : C, D
- Plus économique en mémoire pour les graphes peu denses.
- Se modélise facilement en Python à l'aide d’un dictionnaire.
6️⃣ Passage d’une représentation à une autre
- À partir d’une matrice d’adjacence, on peut déterminer les successeurs d’un sommet en lisant sa ligne.
- À partir des listes de successeurs, on peut reconstruire la matrice.
- Les différentes représentations décrivent le même graphe.
7️⃣ Points essentiels à retenir
- Un graphe est une structure relationnelle.
- Il est constitué de sommets et d’arêtes (ou arcs).
- Un graphe peut être orienté ou non orienté.
- On peut représenter un graphe par une matrice d’adjacence ou une liste de successeurs.
- Ces représentations sont équivalentes.