Au programme de ce chapitre
- I. Vocabulaire et représentations en machine
- II. Parcours en largeur (BFS) et en profondeur (DFS)
- III. Complexité et applications
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition Un graphe est un ensemble de sommets (ou nœuds) reliés par des arêtes. Un graphe est dit non orienté si chaque arête peut être parcourue dans les deux sens, orienté sinon (on parle alors d'arcs). Deux sommets reliés par une arête sont dits adjacents.
🔒 Illustration du chapitre completIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Le graphe non orienté à 6 sommets et 7 arêtes ci-dessous se représente en Python par le dictionnaire :
>>> graphe = {
... "A": ["B", "C"],
... "B": ["A", "D"],
... "C": ["A", "D", "E"],
... "D": ["B", "C", "F"],
... "E": ["C", "F"],
... "F": ["D", "E"],
... }graphe["A"] et dans graphe["B"]), car le graphe est non orienté.Les erreurs fréquentes à éviter
Piège. Matrice O(n²) (dense) vs liste d'adjacence O(n+m) (économe si peu d'arêtes).
L'astuce du prof
Astuce. Orienté (arcs, un sens) vs non orienté (arêtes, deux sens).
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
Différence entre graphe orienté et non orienté ?
Voir la correction
Non orienté : arêtes à double sens ; orienté : arcs à sens unique.
Exercice 2
Compare matrice et liste d'adjacence (mémoire).
Voir la correction
Matrice : O(n²) ; liste : O(n + m).