Chapitre 6 - Révision : Les graphes

---

1. Graphes

• Graphe non orienté : arêtes symétriques
• Graphe orienté : arcs avec un sens

Représentation	Principe	Mémoire	Tester voisinage
Matrice d'adjacence	Tableau 2D de 0 et 1	O(n²)	O(1)
Liste d'adjacence	Dictionnaire sommet → voisins	O(n + m)	O(degré)

Degré : nombre de voisins d'un sommet.

---

2. Algorithmes sur les graphes

Parcours	Structure	Propriété
DFS (profondeur)	Pile / récursion	Trouve un chemin, détecte les cycles
BFS (largeur)	File (FIFO)	Trouve le plus court chemin (en arêtes)

• Cycle : DFS + vérification voisin visité ≠ parent
• Graphe connexe sans cycle = arbre ($n-1$ arêtes pour $n$ sommets)

---

3. Résumé : quelle structure choisir ?

Besoin	Structure
Retour en arrière, annulation	Pile
Traitement dans l'ordre d'arrivée	File
Accès rapide par identifiant	Dictionnaire
Insertions/suppressions en tête	Liste chaînée
Organisation hiérarchique	Arbre
Relations entre éléments	Graphe