Graphes
Les graphes modélisent les relations : réseaux sociaux, cartes routières, internet, molécules... Maîtriser cette structure ouvre les portes à des algorithmes puissants.
Objectifs du cours
- Comprendre la notion de graphe et sa terminologie
- Distinguer graphes orientés et non orientés
- Implémenter un graphe avec matrice d'adjacence et liste d'adjacence
- Appliquer les algorithmes de parcours BFS et DFS
- Résoudre des problèmes classiques sur les graphes
Erreurs courantes à éviter
- Confondre sommet et arête
- Oublier qu'un graphe non orienté a des arêtes dans les deux sens
- Mélanger BFS (file) et DFS (pile)
- Ne pas marquer les sommets visités causant des boucles infinies
Un **graphe** G = (V, E) est composé de : - **V (Vertices/Sommets)** : ensemble des nœuds - **E (Edges/Arêtes)** : ensemble des liaisons entre sommets
**Vocabulaire essentiel** : - **Arête** : liaison entre deux sommets (graphe non orienté) - **Arc** : liaison orientée d'un sommet vers un autre (graphe orienté) - **Degré** d'un sommet : nombre d'arêtes incidentes - **Voisins** : sommets adjacents (reliés par une arête) - **Chemin** : suite de sommets reliés par des arêtes - **Cycle** : chemin qui revient au sommet de départ - **Graphe connexe** : tous les sommets sont reliés (directement ou indirectement) - **Graphe pondéré** : arêtes avec des poids/coûts
# Exemple de graphe : réseau d'amis
#
# Alice ---- Bob
# | \ |
# | \ |
# Charlie -- David
#
# V = {Alice, Bob, Charlie, David}
# E = {(Alice,Bob), (Alice,Charlie), (Alice,David),
# (Bob,David), (Charlie,David)}
#
# Degré d'Alice = 3 (3 amis)
# Degré de Bob = 2 (2 amis)
# Chemin Alice → David : [Alice, David] ou [Alice, Bob, David]
# Cycle : Alice → Bob → David → Alice
# Graphe orienté : followers Twitter
#
# Alice → Bob
# ↑ ↘ ↓
# | ↘ ↓
# Charlie ← David
#
# Alice suit Bob et David
# Bob suit David
# David suit Charlie
# Charlie suit Alice
#
# Arc (Alice, Bob) signifie "Alice suit Bob"
# Ce n'est pas symétrique : Bob ne suit pas forcément AliceQuiz de validation
1. Quelle est la différence entre un graphe orienté et non orienté ?
2. Quelle structure de données utilise le parcours BFS ?
3. Quel parcours est adapté pour trouver le plus court chemin en nombre d'arêtes ?
4. Dans une matrice d'adjacence, que signifie M[i][j] = 1 ?
5. Quel est l'avantage principal de la liste d'adjacence ?
