Le trajet de métro avec le moins d’arrêts
Un graphe représente des lieux et les liens entre eux, comme les stations d’un réseau de transport. Un parcours en largeur trouve le trajet qui passe par le moins de stations.
Les applications de trajet, les réseaux sociaux et les jeux vidéo s’en servent tous les jours.
À la fin de cette leçon
Remarque
Je peux trouver un plus court chemin dans un graphe avec un parcours en largeur.
Mots clés
| Mot | Ce que ça veut dire |
|---|---|
| Graphe | un ensemble de sommets reliés par des arêtes |
| Sommet | un point du graphe, comme une station |
| Arête | un lien entre deux sommets |
| Voisin | un sommet relié directement à un autre |
| Parcours en largeur | on visite d’abord tous les voisins, puis les voisins des voisins |
| Chemin | une suite de sommets où chacun est voisin du suivant |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un graphe se range dans un dictionnaire
Chaque station est un sommet. Chaque ligne entre deux stations est une arête. Deux stations reliées sont voisines.
En Python, on range un graphe dans un dictionnaire. La clé est une station, et la valeur est la liste de ses voisines.
Lance la lecture des voisins
graphe = {
"Gare": ["Mairie", "Halles"],
"Mairie": ["Gare", "Port", "Parc"],
"Halles": ["Gare", "Parc"],
"Port": ["Mairie", "Stade"],
"Parc": ["Mairie", "Halles", "Stade"],
"Stade": ["Port", "Parc"],
}
print(graphe["Mairie"])
print(len(graphe["Parc"]), "voisins pour Parc")
# Affiche les voisins de Stade.
Le parcours en largeur explore par cercles
On part de la station de départ. On visite d’abord ses voisines, puis les voisines de celles-ci, et ainsi de suite.
Une file garde l’ordre : la première station ajoutée est la première explorée. On note les stations déjà vues pour ne pas tourner en rond.
Exemple travaillé : explorer depuis Gare
| Station sortie de la file | Voisines ajoutées | File après |
|---|---|---|
| Gare | Mairie, Halles | Mairie, Halles |
| Mairie | Port, Parc (Gare est déjà vue) | Halles, Port, Parc |
| Halles | aucune, tout est déjà vu | Port, Parc |
| Port | Stade | Parc, Stade |
| Parc | aucune | Stade |
| Stade | aucune | vide |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Lance le parcours en largeur
graphe = {"Gare": ["Mairie", "Halles"], "Mairie": ["Gare", "Port", "Parc"],
"Halles": ["Gare", "Parc"], "Port": ["Mairie", "Stade"],
"Parc": ["Mairie", "Halles", "Stade"], "Stade": ["Port", "Parc"]}
def distances(graphe, depart):
distance = {depart: 0}
file = [depart]
while len(file) > 0:
courant = file.pop(0)
for voisin in graphe[courant]:
if voisin not in distance: # pas encore vue
distance[voisin] = distance[courant] + 1
file.append(voisin)
return distance
print(distances(graphe, "Gare"))
Retrouver le chemin, pas seulement la distance
Pour garder le trajet, on note pour chaque station d’où l’on vient : sa station précédente. À l’arrivée, on remonte de précédente en précédente jusqu’au départ.
On obtient la liste à l’envers, donc on la retourne avec reverse().
Voici la fonction qui renvoie le chemin
def chemin(graphe, depart, arrivee):
precedent = {depart: ""}
file = [depart]
while len(file) > 0:
courant = file.pop(0)
for voisin in graphe[courant]:
if voisin not in precedent:
precedent[voisin] = courant
file.append(voisin)
if arrivee not in precedent:
return [] # aucun trajet
trajet = []
sommet = arrivee
while sommet != "":
trajet.append(sommet)
sommet = precedent[sommet]
trajet.reverse()
return trajet
# chemin(graphe, "Gare", "Stade") donne Gare, Mairie, Port, Stade.
Une erreur fréquente
Attention
Beaucoup pensent que le parcours en largeur trouve le trajet le plus court en kilomètres. Il compte seulement les arêtes : le moins de stations. Pour des distances différentes entre stations, il faut une autre méthode, hors de cette leçon.
Compte les voisines de chaque station
docker exec jupyter python3 -c "g = {'Gare': ['Mairie', 'Halles'], 'Mairie': ['Gare', 'Port', 'Parc'], 'Halles': ['Gare', 'Parc'], 'Port': ['Mairie', 'Stade'], 'Parc': ['Mairie', 'Halles', 'Stade'], 'Stade': ['Port', 'Parc']}; print({k: len(v) for k, v in g.items()}, sum(len(v) for v in g.values()) // 2)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Défile une station avec une vraie file
docker exec jupyter python3 -c "import collections; f = collections.deque(['Gare', 'Mairie']); f.append('Halles'); print(f.popleft(), f)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Ce que disent les deux Runs
Le premier Run range le plan dans un dictionnaire et affiche le nombre de voisines de chaque station, puis le nombre d’arêtes : 7. Mairie et Parc ont chacune trois voisines.
Le second Run utilise collections.deque, une file de Python. Gare et Mairie attendent, Halles arrive derrière. popleft retire Gare, la première arrivée.
Pour aller plus loin : ton propre plan
Dessine le plan de ton lycée ou de ton quartier, avec six lieux et leurs liens. Écris-le en dictionnaire.
Demande à ta fonction le chemin entre deux lieux éloignés. Est-ce le chemin que tu prendrais ?