Algorithmique sur les graphes
Les graphes servent à modéliser des réseaux, des relations ou des déplacements.
1
Représenter un graphe
Types de graphes
Graphe orienté
- Les arêtes ont un sens.
- Un lien A vers B ne vaut pas B vers A.
Graphe non orienté
- Les arêtes n'ont pas de sens.
- Un lien relie les deux sommets dans les deux sens.
Deux représentations classiques
| Représentation | Idée | Atout | Limite |
|---|---|---|---|
| Matrice d'adjacence | Case pour chaque paire de sommets. | Lecture rapide des liens. | Mémoire coûteuse. |
| Liste d'adjacence | Voisins de chaque sommet. | Plus compacte si le graphe est peu dense. | Accès moins direct à une arête précise. |
2
Parcourir le graphe
- 1
Marquer un sommet de départ.
- 2
Explorer ses voisins.
Largeur ou profondeur
Parcours en largeur
- Explore niveau par niveau.
- Utilise une file.
Parcours en profondeur
- Explore une branche jusqu'au bout.
- Utilise une pile ou la récursivité.
Largeur = file ; profondeur = pile.
3
Accessibilité et cycles
- Un sommet est accessible s'il existe un chemin depuis le départ.
- Un parcours montre tous les sommets atteignables.
4
Plus court chemin et complexité
Idée essentielle
Dans un graphe non pondéré, on cherche le chemin le plus court entre deux sommets.
- On lance un parcours en largeur depuis le sommet de départ.
- Les sommets sont découverts par distance croissante.
- Le premier accès au sommet cible donne un plus court chemin en nombre d'arêtes.
En graphe non pondéré, la largeur fournit le plus court chemin en nombre d'arêtes.
On compare le coût d'exécution et la place occupée selon la représentation et l'algorithme.
À retenir
- En graphe pondéré, il faut tenir compte des coûts des arêtes.
- La complexité dépend de la représentation choisie.