08 — Graphes : Cours complet

Niveau : Université / Ingénierie — Durée de lecture : ~65 min

---

Table des matières

1. Définitions
2. Représentations
3. BFS — parcours en largeur
4. DFS — parcours en profondeur
5. Composantes connexes, cycles, bipartition
6. Tri topologique
7. Plus courts chemins : Dijkstra
8. Bellman-Ford : poids négatifs
9. Floyd-Warshall : tous les couples
10. Arbres couvrants minimaux : Kruskal et Prim
11. A* : recherche informée
12. Résumé

---

1. Définitions

Un graphe G = (V, E) : un ensemble de sommets V et d'arêtes E.

• Orienté : chaque arête a un sens (u → v). Ex. : le graphe des routes à sens unique.
• Non orienté : arête = paire {u, v}. Ex. : réseau social (amitié symétrique).
• Pondéré : chaque arête a un poids (distance, coût, capacité).
• DAG : graphe orienté acyclique (ex. : dépendances de compilation).

Diagramme en cours de génération...

• Degré d'un sommet : nombre d'arêtes incidentes (non orienté) / sortantes+entrantes (orienté).
• Chemin : suite de sommets reliés par des arêtes. Cycle : chemin qui revient à son départ.

---

2. Représentations

2.1 Liste d'adjacence

graphe = {
    "A": [("B", 4), ("C", 2)],
    "B": [("D", 1), ("E", 7)],
    "C": [("D", 8), ("E", 3)],
    "D": [],
    "E": [],
}

• Mémoire : O(V + E).
• Parcourir les voisins d'un sommet : O(deg(u)).
• Le plus souvent la meilleure (graphes creux).

2.2 Matrice d'adjacence

INF = float("inf")
m = [
    [0, 4, 2, INF, INF],
    [INF, 0, INF, 1, 7],
    [INF, INF, 0, 8, 3],
    [INF, INF, INF, 0, INF],
    [INF, INF, INF, INF, 0],
]

• Mémoire : O(V²) — indépendant du nombre d'arêtes.
• Tester l'existence d'une arête : O(1).
• Intéressant pour les graphes denses et pour Floyd-Warshall.

2.3 Liste d'arêtes

aretes = [("A", "B", 4), ("A", "C", 2), ("B", "D", 1),
          ("B", "E", 7), ("C", "D", 8), ("C", "E", 3)]

• Mémoire : O(E). Parfait pour Kruskal (on trie les arêtes).
• Ne permet pas de trouver les voisins d'un sommet efficacement.

2.4 Tableau comparatif

---

3. BFS — parcours en largeur

3.1 Principe

Explore le graphe niveau par niveau à partir d'un sommet source. Utilise une file (FIFO, chapitre 05). Marque les sommets dans un ensemble (hash set, chapitre 06) pour éviter les cycles.

Diagramme en cours de génération...

Ordre BFS depuis A : A, B, C, D, E, F.

3.2 Implémentation

from collections import deque

def bfs(graphe, source):
    file = deque([source])
    visites = {source}
    ordre = []
    distance = {source: 0}
    while file:
        u = file.popleft()
        ordre.append(u)
        for v in graphe.get(u, []):
            if v not in visites:
                visites.add(v)
                distance[v] = distance[u] + 1
                file.append(v)
    return ordre, distance

3.3 Propriétés — O(V + E)

• En graphe non pondéré, BFS donne les plus courtes distances en nombre d'arêtes.
• Chaque sommet entre une seule fois dans la file → O(V), chaque arête est examinée une fois → O(E).

---

4. DFS — parcours en profondeur

4.1 Principe

Plonge le plus profond possible avant de revenir. Utilise une pile (ou la récursion — c'est la call stack).

def dfs_recursif(graphe, u, visites=None):
    if visites is None:
        visites = set()
    visites.add(u)
    for v in graphe.get(u, []):
        if v not in visites:
            dfs_recursif(graphe, v, visites)

Version itérative (pile explicite) :

def dfs_iteratif(graphe, source):
    visites = set()
    pile = [source]
    while pile:
        u = pile.pop()
        if u in visites:
            continue
        visites.add(u)
        for v in reversed(graphe.get(u, [])):
            if v not in visites:
                pile.append(v)
    return visites

4.2 Temps de découverte et de fin

def dfs_temps(graphe, source):
    visites = set()
    decouverte = {}
    fin = {}
    temps = 0

    def rec(u):
        nonlocal temps
        visites.add(u)
        temps += 1
        decouverte[u] = temps
        for v in graphe.get(u, []):
            if v not in visites:
                rec(v)
        temps += 1
        fin[u] = temps

    rec(source)
    return decouverte, fin

Propriété : dans un graphe orienté, on détecte un cycle si, pendant DFS, on rencontre une arête vers un sommet « gris » (découvert mais pas fini).

---

5. Composantes connexes, cycles, bipartition

5.1 Composantes connexes (graphe non orienté)

def composantes(graphe):
    visites = set()
    comps = []
    for u in graphe:
        if u not in visites:
            pile = [u]
            comp = []
            visites.add(u)
            while pile:
                x = pile.pop()
                comp.append(x)
                for v in graphe.get(x, []):
                    if v not in visites:
                        visites.add(v)
                        pile.append(v)
            comps.append(comp)
    return comps

O(V + E). Chaque sommet appartient à une unique composante.

5.2 Détection de cycle (graphe non orienté)

Pendant DFS, une arête vers un sommet déjà visité qui n'est pas le parent = cycle.

def a_un_cycle(graphe):
    visites = set()

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

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

5.3 Bipartition

Un graphe est biparti si on peut colorier les sommets en 2 couleurs sans que deux voisins partagent la couleur. Test par BFS/DFS : on colore la source, chaque voisin de la couleur opposée ; conflit = pas biparti.

def est_biparti(graphe):
    couleur = {}
    for source in graphe:
        if source in couleur:
            continue
        couleur[source] = 0
        file = deque([source])
        while file:
            u = file.popleft()
            for v in graphe.get(u, []):
                if v not in couleur:
                    couleur[v] = 1 - couleur[u]
                    file.append(v)
                elif couleur[v] == couleur[u]:
                    return False
    return True

Théorème : un graphe est biparti ssi il ne contient aucun cycle impair. Application : alternance de cours/créneaux, graphe des bipartitions en matching.

---

6. Tri topologique

Ordre linéaire des sommets d'un DAG tel que si u → v, alors u apparaît avant v. Utilisation : ordre de compilation des fichiers dépendants, scheduling, make.

6.1 Par DFS (fin de visite inversée)

def tri_topologique(graphe):
    visites = set()
    ordre = []

    def dfs(u):
        visites.add(u)
        for v in graphe.get(u, []):
            if v not in visites:
                dfs(v)
        ordre.append(u)          # fin de visite

    for u in graphe:
        if u not in visites:
            dfs(u)
    return list(reversed(ordre))

6.2 Par Kahn (indegrés)

from collections import deque

def kahn(graphe):
    indeg = {u: 0 for u in graphe}
    for u in graphe:
        for v in graphe.get(u, []):
            indeg[v] = indeg.get(v, 0) + 1
    file = deque([u for u, d in indeg.items() if d == 0])
    ordre = []
    while file:
        u = file.popleft()
        ordre.append(u)
        for v in graphe.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                file.append(v)
    if len(ordre) != len(graphe):
        return None            # il y a un cycle → pas de tri topologique
    return ordre

Kahn détecte aussi les cycles : si le résultat n'a pas tous les sommets, le graphe contient un cycle.

---

7. Plus courts chemins : Dijkstra

7.1 Principe — poids ≥ 0

Relâchement : à chaque étape, on extrait le sommet non traité de distance minimale (tas min) et on met à jour ses voisins.

import heapq

def dijkstra(graphe, source):
    distance = {u: float("inf") for u in graphe}
    distance[source] = 0
    precedent = {}
    tas = [(0, source)]
    while tas:
        d, u = heapq.heappop(tas)
        if d > distance[u]:
            continue                    # entrée périmée
        for v, w in graphe.get(u, []):
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                precedent[v] = u
                heapq.heappush(tas, (distance[v], v))
    return distance, precedent

7.2 Correctness

La clé : si toutes les pondérations sont ≥ 0, quand on extrait u du tas, distance[u] est définitif (tout autre chemin passant par des sommets non traités ne peut pas faire mieux).

7.3 Complexités

7.4 Limite

Dijkstra échoue avec des poids négatifs : un chemin plus court peut passer par un sommet déjà « finalisé ». → Bellman-Ford.

---

8. Bellman-Ford : poids négatifs

8.1 Principe

On relâche toutes les arêtes V−1 fois. Après i itérations, on connaît les plus courts chemins utilisant ≤ i arêtes. Un chemin simple a au plus V−1 arêtes → V−1 passes suffisent.

def bellman_ford(sommets, aretes, source):
    distance = {u: float("inf") for u in sommets}
    distance[source] = 0
    for _ in range(len(sommets) - 1):
        modifie = False
        for u, v, w in aretes:
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                modifie = True
        if not modifie:
            break
    # détection de cycle négatif
    for u, v, w in aretes:
        if distance[u] + w < distance[v]:
            return None, True           # cycle négatif
    return distance, False

8.2 Complexité

O(V × E) — plus lent que Dijkstra mais accepte les poids négatifs et détecte les cycles négatifs.

8.3 Cas d'usage

• Réseaux : protocole RIP (Distance Vector) — chaque routeur échange des distances avec ses voisins.
• Arbitrage de devises : chercher un cycle de taux de change profitable (cycle négatif en log).

---

9. Floyd-Warshall : tous les couples

9.1 Principe

Programmation dynamique sur les sommets intermédiaires : D[k][i][j] = plus court chemin de i à j en n'utilisant que les sommets 1..k.

En place (matrice) :

def floyd_warshall(n, matrice):
    D = [row[:] for row in matrice]          # copie
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if D[i][k] + D[k][j] < D[i][j]:
                    D[i][j] = D[i][k] + D[k][j]
    return D

9.2 Complexité

O(V³) temps, O(V²) mémoire. Adapté aux graphes denses ou aux petits graphes où on veut tous les couples de plus courts chemins.

Détection de cycle négatif : après l'algorithme, si D[i][i] < 0 pour un i, il existe un cycle négatif.

---

10. Arbres couvrants minimaux : Kruskal et Prim

Un arbre couvrant relie tous les sommets sans cycle. Le minimum spanning tree (MST) minimise la somme des poids. Applications : réseaux électriques, câblage, clusters.

10.1 Kruskal — O(E log E) via union-find

On trie les arêtes par poids croissant et on les ajoute si elles ne créent pas de cycle (union-find).

class UnionFind:
    def __init__(self, sommets):
        self.parent = {u: u for u in sommets}
        self.rank = {u: 0 for u in sommets}

    def trouver(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.trouver(self.parent[x])   # path compression
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.trouver(a), self.trouver(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

def kruskal(sommets, aretes):
    uf = UnionFind(sommets)
    mst = []
    for u, v, w in sorted(aretes, key=lambda a: a[2]):
        if uf.union(u, v):
            mst.append((u, v, w))
    return mst

Union-find : avec compression de chemin + union par rang, chaque opération est ~O(α(n)) (inverse de la fonction d'Ackermann, en pratique O(1)).

10.2 Prim — O((V + E) log V) via tas min

On part d'un sommet et on ajoute à chaque fois l'arête de poids minimal reliant l'arbre au reste.

def prim(graphe, source):
    visites = {source}
    tas = []
    for v, w in graphe.get(source, []):
        heapq.heappush(tas, (w, source, v))
    mst = []
    while tas:
        w, u, v = heapq.heappop(tas)
        if v in visites:
            continue
        visites.add(v)
        mst.append((u, v, w))
        for x, wx in graphe.get(v, []):
            if x not in visites:
                heapq.heappush(tas, (wx, v, x))
    return mst

10.3 Kruskal vs Prim

---

11. A* : recherche informée

11.1 Principe

Comme Dijkstra, mais avec une heuristique h(u) = estimation du coût restant jusqu'au but. On extrait le nœud minimisant f(u) = g(u) + h(u) (coût déjà parcouru + estimation).

def astar(graphe, source, but, h):
    open_set = [(h(source), source)]
    g = {source: 0}
    precedent = {}
    while open_set:
        f, u = heapq.heappop(open_set)
        if u == but:
            return g[u], precedent
        for v, w in graphe.get(u, []):
            candidat = g[u] + w
            if candidat < g.get(v, float("inf")):
                g[v] = candidat
                precedent[v] = u
                heapq.heappush(open_set, (candidat + h(v), v))
    return float("inf"), {}

11.2 Admissibilité

• h est admissible si h(u) ≤ vrai coût restant (ex. : distance euclidienne en ligne droite sur une carte). Alors A* est optimal (il trouve le plus court chemin).
• Si h(u) = 0 partout, A* = Dijkstra.
• En navigation GPS, A* visite beaucoup moins de nœuds que Dijkstra.

---

12. Résumé

1. Représentations : liste d'adjacence O(V+E) pour les graphes creux ; matrice O(V²) pour les denses ; liste d'arêtes pour les tris.
2. BFS : file, plus courtes distances (non pondéré), O(V+E).
3. DFS : pile/récursion, temps de découverte/fin, détection de cycles.
4. Connexité / bipartition : une passe de parcours par composante ; 2-coloriage.
5. Tri topologique : DFS inversé ou Kahn (qui détecte les cycles).
6. Dijkstra : tas min, O((V+E) log V), poids ≥ 0 uniquement.
7. Bellman-Ford : O(VE), poids négatifs, détection de cycles négatifs.
8. Floyd-Warshall : O(V³), tous les couples, cycle négatif si D[i][i] < 0.
9. MST : Kruskal (union-find, tri des arêtes) ; Prim (tas min).
10. A* : heuristique admissible → optimal, plus efficace que Dijkstra en pratique.

---

Exercices d'auto-évaluation

1. Quand choisir la matrice d'adjacence plutôt que la liste ?
2. Pourquoi Dijkstra échoue-t-il avec des poids négatifs ?
3. Combien de passes dans Bellman-Ford et pourquoi ?
4. Comment détecter un cycle dans un graphe orienté ? Non orienté ?
5. Que retourne l'algorithme de Kahn si le graphe contient un cycle ?
6. Pourquoi la compression de chemin rend-elle union-find quasi-constant ?
7. Quelle condition sur h garantit l'optimalité de A* ?

Passez au quiz puis aux TP.