Algorithmique sur les graphes : parcours, plus court chemin

Introduction

Les graphes sont des structures mathématiques fondamentales qui modélisent des relations entre objets. Dans le contexte de l'algorithmique, ils nous permettent de résoudre des problèmes complexes liés à la navigation, à la communication ou à l'optimisation. Ce cours se penche sur les parcours de graphes et les algorithmes de plus court chemin, essentiels pour comprendre comment naviguer efficacement dans des réseaux.

1. Notions de base sur les graphes

Un graphe est constitué de sommets (ou nœuds) et d'arêtes (ou liens) qui les relient. On peut représenter un graphe de plusieurs façons, notamment par une matrice d'adjacence ou une liste d'adjacence.

1.1 Types de graphes

• Graphe orienté : les arêtes ont une direction.


• Graphe non orienté : les arêtes n'ont pas de direction.


• Graphe pondéré : les arêtes ont des poids (valeurs) associés, représentant par exemple des distances ou des coûts.

#### Exemple concret
Considérons un graphe représentant un réseau routier entre plusieurs villes. Les sommets représentent les villes et les arêtes représentent les routes entre elles, avec des poids correspondant aux distances en kilomètres.

2. Parcours de graphes

Le parcours d'un graphe consiste à explorer ses sommets de manière systématique. Deux algorithmes courants sont le parcours en profondeur (DFS) et le parcours en largeur (BFS).

2.1 Parcours en profondeur (DFS)

Cet algorithme explore un chemin jusqu'à ce qu'il atteigne un sommet sans voisins non visités, puis il revient en arrière pour explorer d'autres chemins.