Graphes et parcours
Fiche compacte sur les graphes, leur représentation et leurs parcours.
1
Graphe et représentation
Bases
Un graphe relie des sommets par des arêtes.
- Sommet = nœud du graphe.
- Arête = lien entre deux sommets.
Stockage
Liste d’adjacence
- Mémorise les voisins.
- Adaptée aux graphes clairsemés.
- Parcours souvent efficace.
Matrice d’adjacence
- Indique chaque paire de sommets.
- Accès rapide à une arête.
- Coûte plus de mémoire.
2
BFS
Parcours en largeur
- 1
Marquer la source visitée.
- 2
Ajouter la source dans une file FIFO.
- 3
Retirer un sommet de la file.
Idée à retenir
BFS explore par niveaux : file, voisinage proche, distance minimale.
3
DFS
Parcours en profondeur
- 1
Marquer le sommet courant.
- 2
Aller vers un voisin non visité.
- 3
Continuer jusqu’au blocage.
Idée à retenir
DFS descend au plus profond avant de remonter.
4
Composantes et distance
Relations utiles
Usage
- Une composante connexe regroupe des sommets reliés.
- BFS ou DFS identifie les composantes connexes.
5
Complexité et points clés
Comparaison
| Parcours | File ou pile | Rôle principal | Complexité |
|---|---|---|---|
| BFS | File FIFO | Distances | O(|V| + |E|) |
| DFS | Pile ou récursion | Exploration | O(|V| + |E|) |
Résumé
- Sommets et arêtes définissent le graphe.
- La représentation choisie change l’efficacité.