%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]]
%% nav-fin %%
# Labyrinthe - distance (BFS)
## 🎯 Objectif
Mettre en œuvre un parcours en largeur (**BFS**) pour calculer la **distance minimale** (nombre d’arêtes / de déplacements) entre deux sommets d’un graphe représentant un **labyrinthe**.
## 📄 Énoncé
On considère un **graphe** `D` (dictionnaire d’adjacence) représentant un labyrinthe :
- chaque sommet est une case (ou un identifiant de case),
- `D[u]` contient l'ensemble des voisins accessibles depuis `u`.
On souhaite écrire une fonction `distance(D, debut, fin)` qui :
- explore le graphe à partir de `debut`,
- calcule pour chaque sommet atteint sa distance à `debut`,
- renvoie la distance minimale pour atteindre `fin` si `fin` est atteignable,
- sinon renvoie `False`.
👉 L’algorithme attendu est un **BFS** (file d’exploration), qui garantit une distance minimale dans un graphe non pondéré.
## 🔍 Avant de programmer
Le labyrinthe de l'atelier compte 36 cases, numérotées ligne par ligne de 1 à 36. Deux cases sont voisines dans le graphe quand aucun mur ne les sépare.
**À manipuler :** suivez le parcours en largeur de la case 1 à la case 36. Le nombre affiché dans une case découverte est sa distance à la case 1. À la fin, le chemin est reconstruit en remontant les parents.
```sq-labyrinthe
départ: 1
arrivée: 36
parcours: largeur
```
## 🧩 Travail demandé
1. Exécuter la cellule de préparation, qui construit le graphe `D` du labyrinthe.
2. Implémenter `distance(D, debut, fin)` par un parcours en largeur.
3. Tester la fonction sur un cas où `fin` est atteignable et sur un cas où elle ne l'est pas.
4. (Bonus) Écrire `chemin(D, debut, fin)`, qui reconstruit un plus court chemin en remontant les parents depuis `fin`.
5. (Pour aller plus loin) Compter les composantes connexes d'un graphe avec le même parcours.
## 💻 Programmer dans la page
Les cellules s'exécutent dans le navigateur. Elles partagent les mêmes variables : exécutez-les dans l'ordre. Le premier lancement charge Python en quelques secondes.
**Préparation :** le labyrinthe compte 36 cases, numérotées ligne par ligne de 1 à 36. Chaque couple de `passages` relie deux cases voisines sans mur entre elles. `D` est le dictionnaire d'adjacence : `D[u]` est l'ensemble des cases accessibles depuis `u`.
```sq-python
passages = [(1, 2), (2, 3), (3, 9), (4, 5), (4, 10), (5, 6), (6, 12), (7, 8), (7, 13),
(8, 9), (9, 15), (10, 16), (11, 17), (12, 18), (13, 19), (14, 20), (15, 16),
(17, 23), (18, 24), (19, 20), (19, 25), (21, 22), (21, 27), (22, 23), (24, 30),
(25, 31), (26, 27), (26, 32), (27, 33), (28, 29), (28, 34), (29, 30), (31, 32),
(33, 34), (34, 35), (35, 36)]
D = {case: set() for case in range(1, 37)}
for a, b in passages:
D[a].add(b)
D[b].add(a)
print(sorted(D[9]))
#--- sortie
[3, 8, 15]
```
**Dessin du graphe (facultatif) :** `networkx` place les sommets et `matplotlib` dessine la figure sous la cellule.
```sq-python
import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph(D)
pos = nx.kamada_kawai_layout(G)
nx.draw(G, pos, with_labels=True, node_color="#F0F3F7", edgecolors="#4D6386", node_size=420)
plt.show()
```
**Question 1 :** écrivez `distance(D, debut, fin)`. La fonction renvoie le nombre de déplacements du plus court chemin, ou `False` si `fin` n'est pas atteignable.
```sq-python
from collections import deque
def distance(D, debut, fin):
dist = {debut: 0} # sommets découverts et leur distance à debut
file = deque([debut])
# À compléter : défiler un sommet, découvrir ses voisins
return False
print("Distance de 1 à 36 :", distance(D, 1, 36))
#--- correction
from collections import deque
def distance(D, debut, fin):
dist = {debut: 0} # sommets découverts et leur distance à debut
file = deque([debut])
while file:
u = file.popleft() # on défile le sommet en tête
for v in sorted(D[u]):
if v not in dist: # v n'est pas encore découvert
dist[v] = dist[u] + 1
file.append(v)
if fin in dist:
return dist[fin]
return False
print("Distance de 1 à 36 :", distance(D, 1, 36))
#--- tests
assert distance(D, 1, 36) == 16, "la distance de 1 à 36 doit valoir 16"
assert distance(D, 36, 1) == 16, "la distance de 36 à 1 doit aussi valoir 16"
assert distance(D, 1, 1) is not False and distance(D, 1, 1) == 0, "la distance d'une case à elle-même vaut 0"
assert distance(D, 1, 2) == 1, "deux cases reliées par un passage sont à distance 1"
assert distance({1: {2}, 2: {1}, 3: set()}, 1, 3) is False, "une case inatteignable doit donner False"
```
**Question 2 (bonus) :** écrivez `chemin(D, debut, fin)`. Le parcours retient le parent de chaque sommet découvert ; on remonte ensuite de `fin` à `debut`.
```sq-python
def chemin(D, debut, fin):
parent = {debut: None}
# À compléter
return False
print(chemin(D, 1, 36))
#--- correction
def chemin(D, debut, fin):
parent = {debut: None}
file = deque([debut])
while file:
u = file.popleft()
for v in sorted(D[u]):
if v not in parent:
parent[v] = u
file.append(v)
if fin not in parent:
return False
c = [fin]
while c[-1] != debut: # on remonte les parents depuis fin
c.append(parent[c[-1]])
return list(reversed(c))
print(chemin(D, 1, 36))
#--- tests
assert chemin(D, 1, 36) == [1, 2, 3, 9, 8, 7, 13, 19, 25, 31, 32, 26, 27, 33, 34, 35, 36], "le chemin de 1 à 36 n'est pas le bon"
assert len(chemin(D, 1, 36)) == distance(D, 1, 36) + 1, "un chemin de distance d contient d + 1 cases"
assert chemin({1: {2}, 2: {1}, 3: set()}, 1, 3) is False, "une case inatteignable doit donner False"
```
### Pour aller plus loin : les composantes connexes
Une composante connexe est un ensemble maximal de sommets reliés entre eux par des chemins. Un parcours en largeur depuis un sommet découvre exactement sa composante. On compte les composantes en lançant un parcours depuis chaque sommet encore non découvert.
Le graphe `D2` ci-dessous a trois composantes : {A, B, F, G}, {C, D} et {E}.
**Question 3 :** écrivez `composantes(D)`, qui renvoie un dictionnaire associant à chaque sommet le numéro de sa composante, à partir de 1.
```sq-python
D2 = {
"A": {"B", "F", "G"},
"B": {"A", "F"},
"C": {"D"},
"D": {"C"},
"E": set(),
"F": {"A", "B"},
"G": {"A"},
}
def composantes(D):
numero = {}
c = 0
# À compléter : pour chaque sommet non numéroté, c += 1 puis parcours en largeur
return numero
print(composantes(D2))
#--- correction
D2 = {
"A": {"B", "F", "G"},
"B": {"A", "F"},
"C": {"D"},
"D": {"C"},
"E": set(),
"F": {"A", "B"},
"G": {"A"},
}
def composantes(D):
numero = {}
c = 0
for s in sorted(D):
if s in numero:
continue
c += 1 # nouvelle composante
numero[s] = c
file = deque([s])
while file:
u = file.popleft()
for v in D[u]:
if v not in numero:
numero[v] = c
file.append(v)
return numero
print(composantes(D2))
#--- tests
assert max(composantes(D2).values()) == 3, "D2 a 3 composantes connexes"
assert composantes(D2)["A"] == composantes(D2)["G"], "A et G sont dans la même composante"
assert composantes(D2)["C"] != composantes(D2)["A"], "C n'est pas dans la composante de A"
assert max(composantes(D).values()) == 1, "le labyrinthe est connexe : une seule composante"
```
Dans un graphe orienté, on obtient les composantes au sens faible en ignorant le sens des arcs : on ajoute à chaque arc `u → v` l'arc `v → u`, puis on applique `composantes`.
## 🧠 À retenir
- Un parcours **BFS** explore le graphe **par couches** : distance 0, puis 1, puis 2, etc.
- Dans un graphe **non pondéré**, BFS permet d’obtenir la **distance minimale**.
- Le dictionnaire `dist` joue deux rôles : il donne la distance de chaque case découverte, et il indique si une case est déjà découverte.
- `deque` du module `collections` défile en tête sans décaler les éléments, comme dans la page [[Code et Développement/Programmation/Graphes/03_Parcours en largeur (BFS)|Parcours en largeur]].
%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]]
%% nav-fin %%
---
🗓️ Historique
Dernière mise à jour : `8 novembre 2026`
Rédigé par : [[Julien DUQUENNOY]]