Graphes : tout est réseau.

• Choisir liste d’adjacence ou matrice selon la densité.
• Implémenter 8 algorithmes de graphes et connaître leur complexité.
• Modéliser un problème concret (planification de robot, réseau de capteurs, dépendances) en graphe.

Références : CLRS chapitres 22-26, programme MPI « graphes », Sedgewick Algorithms partie 4.

Un graphe routier de 10⁷ sommets a ~2·10⁷ arêtes : la matrice pèserait 10¹⁴ cases. La liste d’adjacence est le choix par défaut.

Un sommet gris est sur la pile d’appels courante. Rencontrer une arête vers un sommet gris, c’est revenir sur un ancêtre : un cycle. Le tri topologique est l’ordre inverse des dates de fin : quand u finit, tous ses descendants ont fini avant lui. Applications : make, gestionnaires de paquets, ordonnancement de calculs (PyTorch construit et trie topologiquement le graphe des opérations pour la rétropropagation, module L14). La version récursive dépasse la limite de pile pour ~1000 sommets : en pratique on écrit une version itérative avec une pile explicite.

Quand un sommet u sort du tas avec la distance d, aucune autre voie ne peut être plus courte : tout autre chemin vers u passe par un sommet encore dans le tas, dont la distance est ≥ d, plus des poids ≥ 0. Cette preuve échoue avec des poids négatifs (ici, Dijkstra fixe B à 5 avant de découvrir A→C→B = −2 ; par chance la version « paresseuse » ci-dessus se corrige, mais ce n’est pas garanti en général). Dijkstra est un glouton dont l’argument d’échange repose sur la positivité. Pour un GPS : contraction hierarchies, A* et pré-calculs rendent Dijkstra 1000 fois plus rapide sur un graphe continental.

A* trie par f = g + h : coût déjà payé + estimation du reste. Si h ne sur-estime jamais (admissible), le premier chemin trouvé est optimal. Si de plus h(u) ≤ coût(u, v) + h(v) (consistante, inégalité triangulaire), chaque sommet est sorti une seule fois. La distance euclidienne est admissible pour tout déplacement ; l’octile est plus serrée pour 8 directions, donc explore moins. Une heuristique qui sur-estime (h × 1,5) va plus vite mais peut rater l’optimum : c’est le « weighted A* » des jeux vidéo, où la vitesse prime. Sur un robot, A* tourne sur une grille d’occupation (module L20) ; en 3D et avec des contraintes cinématiques, on passe aux RRT (module L21).

Le flot maximal égale la capacité de la coupe minimale (théorème de Ford-Fulkerson) : le goulot d’étranglement d’un réseau est exactement son débit maximal. Applications : bande passante, affectation (couplage biparti), segmentation d’images (graph cuts), planification de projets, et beaucoup de problèmes qui ne ressemblent pas à des flots mais s’y réduisent — reconnaître ces réductions est un art de concours.

def est_biparti(adj):
    couleur = {}
    for s in adj:
        if s in couleur: continue
        couleur[s] = 0; file = deque([s])
        while file:
            u = file.popleft()
            for v in adj[u]:
                if v not in couleur: couleur[v] = 1 - couleur[u]; file.append(v)
                elif couleur[v] == couleur[u]: return False
    return True
def echelle(depart, arrivee, mots):
    D = set(mots) | {depart}; pred = {depart: None}; file = deque([depart])
    while file:
        u = file.popleft()
        if u == arrivee: break
        for i in range(len(u)):
            for c in "abcdefghijklmnopqrstuvwxyz":
                v = u[:i] + c + u[i + 1:]
                if v in D and v not in pred: pred[v] = u; file.append(v)
    if arrivee not in pred: return None
    c, u = [], arrivee
    while u: c.append(u); u = pred[u]
    return c[::-1]

def duree_projet(taches):
    ordre, vus = [], set()
    def visiter(t):
        if t in vus: return
        vus.add(t)
        for p in taches[t][1]: visiter(p)
        ordre.append(t)
    for t in taches: visiter(t)
    debut = {}
    for t in ordre: debut[t] = max((debut[p] + taches[p][0] for p in taches[t][1]), default=0)
    fin_projet = max(debut[t] + taches[t][0] for t in taches)
    tard = {}                                          # au plus tard : en ordre inverse
    for t in reversed(ordre):
        succ = [s for s in taches if t in taches[s][1]]
        tard[t] = min((tard[s] for s in succ), default=fin_projet) - taches[t][0]
    return fin_projet, sorted(t for t in taches if debut[t] == tard[t])

def chemin_moins_de_k_aretes(adj, s, t, k):
    dist = {(s, 0): 0}; tas = [(0, s, 0)]
    while tas:
        d, u, n = heapq.heappop(tas)
        if u == t: return d
        if d > dist.get((u, n), float("inf")) or n == k: continue
        for v, p in adj[u]:
            if d + p < dist.get((v, n + 1), float("inf")):
                dist[(v, n + 1)] = d + p; heapq.heappush(tas, (d + p, v, n + 1))
    return None
def kruskal(n, aretes):
    parent = list(range(n))
    def trouver(x):
        while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]
        return x
    total, nb = 0, 0
    for u, v, p in sorted(aretes, key=lambda a: a[2]):
        ru, rv = trouver(u), trouver(v)
        if ru != rv: parent[ru] = rv; total += p; nb += 1
    return total if nb == n - 1 else None

class G:
    def voisins(self, m): return voisins(m)
    def sommets(self): return mots
g2 = G()
dist, pred = bfs(g2, "froid")
print(chemin(pred, "chaud") if "chaud" in dist else "pas de chemin")
print("composantes :", composantes_connexes(g2))
exc = {m: max(bfs(g2, m)[0].values()) for m in mots if len(bfs(g2, m)[0]) > 1}
print(min(exc, key=exc.get), exc)

Construire le graphe explicitement coûterait O(n²·L) comparaisons ; pour un vrai dictionnaire (300 000 mots), on hache les motifs « fr_id » pour trouver les voisins en O(L) par mot.

def successeurs(etat):
    i, j, d = etat
    di, dj = DIRS[d]
    a, b = i + di, j + dj
    if 0 <= a < len(labyrinthe) and 0 <= b < len(labyrinthe[0]) and labyrinthe[a][b] != "#":
        yield (a, b, d), 1
    k = ORDRE.index(d)
    yield (i, j, ORDRE[(k + 1) % 4]), 2
    yield (i, j, ORDRE[(k - 1) % 4]), 2

def dijkstra_etats(depart, est_but):
    dist, pred, tas = {depart: 0}, {depart: None}, [(0, depart)]
    while tas:
        d, u = heapq.heappop(tas)
        if d > dist[u]: continue
        if est_but(u):
            c = []
            while u: c.append(u); u = pred[u]
            return d, c[::-1]
        for v, p in successeurs(u):
            if d + p < dist.get(v, float("inf")):
                dist[v], pred[v] = d + p, u; heapq.heappush(tas, (d + p, v))

cout, traj = dijkstra_etats((0, 0, "E"), lambda e: e[:2] == (4, 8))
print("coût :", cout, "| virages :", sum(1 for a, b in zip(traj, traj[1:]) if a[2] != b[2]))
print([e[:2] for e in traj if True][::3])

L’espace d’états est 4 fois plus grand que la grille, mais Dijkstra reste instantané. C’est exactement ainsi qu’un planificateur de robot (ROS Nav2, module L21) intègre les contraintes cinématiques : l’état n’est pas la position mais (position, cap, vitesse…).

def deux_sat(clauses):
    g = Graphe(oriente=True)
    for a, b in clauses:
        g.ajouter_arete(-a, b); g.ajouter_arete(-b, a)
    for a, b in clauses:
        for x in (a, b, -a, -b): g.adj[x]
    comps = kosaraju(g)
    cfc = {}
    for i, c in enumerate(comps):
        for x in c: cfc[x] = i
    for x in list(cfc):
        if x > 0 and -x in cfc and cfc[x] == cfc[-x]: return None
    # Kosaraju renvoie les CFC en ordre topologique du graphe : x vrai si cfc[x] > cfc[-x]
    return {x: cfc[x] > cfc[-x] for x in cfc if x > 0}

print(deux_sat(clauses_ok)); print(deux_sat(clauses_ko))
aff = deux_sat(clauses_ok)
val = lambda l: aff[abs(l)] if l > 0 else not aff[abs(l)]
print("vérification :", all(val(a) or val(b) for a, b in clauses_ok))

Avec 2 littéraux, une clause est une implication et le problème devient un problème de graphe. Avec 3, il n’y a plus de structure d’implication simple : 3-SAT est le problème NP-complet de référence (Cook-Levin, module L23). Cette frontière — un problème facile, son voisin immédiat difficile — est l’un des phénomènes centraux de l’informatique théorique.