Chapitre 6 - Partie 3 : Algorithmes sur les graphes

B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale

Contenus	Capacités attendues	Commentaires
Algorithmes sur les graphes.	Parcourir un graphe en profondeur d'abord, en largeur d'abord. Repérer la présence d'un cycle dans un graphe. Chercher un chemin dans un graphe.	Le parcours d'un labyrinthe et le routage dans Internet sont des exemples d'algorithme sur les graphes. L'exemple des graphes permet d'illustrer l'utilisation des classes en programmation.

1. Rappels sur les graphes

1.1 Représentations

Un graphe peut être représenté par :

une matrice d'adjacence : tableau 2D où matrice[i][j] = 1 si les sommets i et j sont reliés ;
un dictionnaire de listes d'adjacence : pour chaque sommet, la liste de ses voisins.

# Graphe non orienté
#   A --- B
#   |   / |
#   |  /  |
#   C --- D

# Dictionnaire d'adjacence
graphe = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

# Matrice d'adjacence (A=0, B=1, C=2, D=3)
matrice = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 1],
    [0, 1, 1, 0]
]

2. Parcours en profondeur (DFS)

2.1 Principe

Le parcours en profondeur (Depth-First Search, DFS) explore un graphe en allant le plus loin possible avant de revenir en arrière. Il utilise une pile (ou la récursion).

2.2 Algorithme récursif

def dfs_recursif(graphe, sommet, visites=None):
    if visites is None:
        visites = set()
    visites.add(sommet)
    print(sommet, end=' ')
    for voisin in graphe[sommet]:
        if voisin not in visites:
            dfs_recursif(graphe, voisin, visites)
    return visites

>>> dfs_recursif(graphe, 'A')
A B C D

2.3 Algorithme itératif (avec pile)

def dfs_iteratif(graphe, depart):
    visites = set()
    pile = [depart]
    resultat = []
    while pile:
        sommet = pile.pop()
        if sommet not in visites:
            visites.add(sommet)
            resultat.append(sommet)
            for voisin in reversed(graphe[sommet]):
                if voisin not in visites:
                    pile.append(voisin)
    return resultat

2.4 Application : le labyrinthe

Un labyrinthe peut être modélisé comme un graphe où chaque case est un sommet et les passages sont des arêtes. Le DFS permet de trouver un chemin de l'entrée à la sortie.

3. Parcours en largeur (BFS)

3.1 Principe

Le parcours en largeur (Breadth-First Search, BFS) explore un graphe niveau par niveau : d'abord les voisins directs, puis les voisins des voisins, etc. Il utilise une file (FIFO).

3.2 Algorithme

from collections import deque

def bfs(graphe, depart):
    visites = set([depart])
    file = deque([depart])
    resultat = []
    while file:
        sommet = file.popleft()
        resultat.append(sommet)
        for voisin in graphe[sommet]:
            if voisin not in visites:
                visites.add(voisin)
                file.append(voisin)
    return resultat

>>> bfs(graphe, 'A')
['A', 'B', 'C', 'D']

3.3 Comparaison DFS vs BFS

Critère	DFS (profondeur)	BFS (largeur)
Structure	Pile (ou récursion)	File
Exploration	En profondeur d'abord	Niveau par niveau
Chemin trouvé	Un chemin (pas forcément le plus court)	Le plus court chemin (en nombre d'arêtes)
Mémoire	Proportionnelle à la hauteur	Proportionnelle à la largeur

4. Chercher un chemin

4.1 Chemin entre deux sommets (DFS)

def chemin_dfs(graphe, depart, arrivee, visites=None):
    if visites is None:
        visites = set()
    visites.add(depart)
    if depart == arrivee:
        return [depart]
    for voisin in graphe[depart]:
        if voisin not in visites:
            chemin = chemin_dfs(graphe, voisin, arrivee, visites)
            if chemin is not None:
                return [depart] + chemin
    return None

>>> chemin_dfs(graphe, 'A', 'D')
['A', 'B', 'C', 'D']    # un chemin possible

4.2 Plus court chemin (BFS)

Le BFS garantit de trouver le plus court chemin (en nombre d'arêtes).

from collections import deque

def plus_court_chemin(graphe, depart, arrivee):
    if depart == arrivee:
        return [depart]
    visites = {depart}
    file = deque([(depart, [depart])])
    while file:
        sommet, chemin = file.popleft()
        for voisin in graphe[sommet]:
            if voisin not in visites:
                nouveau_chemin = chemin + [voisin]
                if voisin == arrivee:
                    return nouveau_chemin
                visites.add(voisin)
                file.append((voisin, nouveau_chemin))
    return None

>>> plus_court_chemin(graphe, 'A', 'D')
['A', 'B', 'D']    # le plus court (2 arêtes)

5. Détecter un cycle

5.1 Cycle dans un graphe non orienté

Un cycle est un chemin qui revient à son point de départ. Pour le détecter dans un graphe non orienté, on effectue un DFS : si on rencontre un sommet déjà visité qui n'est pas le parent direct, il y a un cycle.

def contient_cycle(graphe):
    visites = set()

    def dfs(sommet, parent):
        visites.add(sommet)
        for voisin in graphe[sommet]:
            if voisin not in visites:
                if dfs(voisin, sommet):
                    return True
            elif voisin != parent:
                return True
        return False

    for sommet in graphe:
        if sommet not in visites:
            if dfs(sommet, None):
                return True
    return False

>>> contient_cycle(graphe)
True    # A-B-C-A forme un cycle

5.2 Graphe sans cycle (arbre)

Un graphe connexe sans cycle est un arbre. Il a exactement $n - 1$ arêtes pour $n$ sommets.

6. Applications

Application	Graphe	Algorithme
Labyrinthe	Cases = sommets, passages = arêtes	DFS ou BFS
GPS / Itinéraire	Carrefours = sommets, routes = arêtes pondérées	Dijkstra (BFS pondéré)
Réseau social	Personnes = sommets, relations = arêtes	BFS (degré de séparation)
Routage Internet	Routeurs = sommets, liens = arêtes	OSPF (Dijkstra), RIP (Bellman-Ford)
Ordonnancement	Tâches = sommets, dépendances = arcs	Tri topologique (DFS)

Parcours de graphe animé : activez JavaScript pour utiliser cette visualisation.

À retenir

Concept	Description
DFS	Parcours en profondeur, utilise une pile ou la récursion
BFS	Parcours en largeur, utilise une file, trouve le plus court chemin
Cycle	Chemin revenant au point de départ (DFS pour détecter)
Chemin	Suite de sommets reliés par des arêtes
Plus court chemin	Chemin avec le minimum d'arêtes (BFS) ou de coût (Dijkstra)