🕸️

Graphes

Représentations, parcours BFS/DFS, Dijkstra

Graphes orientés BFS / DFS Dijkstra

🎯 Introduction

Un graphe est un ensemble de sommets (nœuds) reliés par des arêtes (arcs si orienté). Les graphes modélisent les réseaux routiers, sociaux, Internet, les dépendances entre tâches...

✅ Ce qu'il faut savoir

Deux représentations : matrice d'adjacence et liste d'adjacence
Différence graphe orienté / non orienté / pondéré
BFS (parcours en largeur) avec une file
DFS (parcours en profondeur) avec récursion ou pile
Algorithme de Dijkstra (plus courts chemins, poids positifs)
Notions : connexité, cycle, chemin

📐 Représentations

Chaque sommet est associé à la liste de ses voisins. Efficace pour les graphes creux.

# Graphe non orienté
graphe = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# Graphe pondéré orienté
graphe_p = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 5)],
    'C': [('B', 1), ('D', 8)],
    'D': []
}

Opération	Complexité
Voisins d'un sommet	O(degré)
Tester si arête (u,v)	O(degré)
Espace mémoire	O(V + E)

Matrice n×n : M[i][j] = 1 si arête de i vers j. Efficace pour les graphes denses.

# Graphe avec 4 sommets : 0,1,2,3
matrice = [
    [0, 1, 1, 0],   # 0 → 1, 0 → 2
    [1, 0, 0, 1],   # 1 → 0, 1 → 3
    [1, 0, 0, 1],   # 2 → 0, 2 → 3
    [0, 1, 1, 0]    # 3 → 1, 3 → 2
]
# Tester l'arête (0, 1) :
matrice[0][1] == 1   # True — O(1)

Opération	Complexité
Tester si arête (u,v)	O(1)
Voisins d'un sommet	O(V)
Espace mémoire	O(V²)

🔄 Parcours : BFS et DFS

from collections import deque

# BFS — Parcours en Largeur (Breadth-First Search)
# Utilise une FILE. Trouve le plus court chemin (non pondéré).
def bfs(graphe, depart):
    visites = {depart}
    file = deque([depart])
    while file:
        s = file.popleft()
        print(s)
        for voisin in graphe[s]:
            if voisin not in visites:
                visites.add(voisin)
                file.append(voisin)

# DFS — Parcours en Profondeur (Depth-First Search)
# Utilise la RÉCURSION (ou une pile). Explore le plus loin possible.
def dfs(graphe, s, visites=None):
    if visites is None: visites = set()
    visites.add(s)
    print(s)
    for voisin in graphe[s]:
        if voisin not in visites:
            dfs(graphe, voisin, visites)
    return visites

	BFS	DFS
Structure	File (deque)	Récursion / pile
Plus court chemin	✅ Oui (non pondéré)	❌ Non
Détection de cycle	✅ Oui	✅ Oui
Complexité	O(V + E)	O(V + E)

🗺️ Algorithme de Dijkstra

⚠️

Condition d'utilisation

Dijkstra ne fonctionne qu'avec des poids positifs ou nuls. Pour les poids négatifs, utiliser Bellman-Ford.

import heapq

def dijkstra(graphe, depart):
    # graphe[s] = [(voisin, poids), ...]
    dist = {s: float('inf') for s in graphe}
    dist[depart] = 0
    tas = [(0, depart)]
    while tas:
        d, u = heapq.heappop(tas)
        if d > dist[u]: continue  # entrée obsolète
        for v, poids in graphe[u]:
            nd = dist[u] + poids
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(tas, (nd, v))
    return dist

📌 Propriétés importantes

Propriété	Définition	Test
Connexe	Tout sommet est atteignable depuis n'importe quel autre	BFS/DFS depuis un sommet visite tous les sommets
Acyclique	Pas de cycle (chemin qui revient au départ)	DFS sans marquer → si on revisite → cycle
DAG	Directed Acyclic Graph : orienté et sans cycle	Tri topologique possible
Arbre	Connexe et acyclique	n sommets, n-1 arêtes

🚨

Pièges du bac

Oublier de marquer les sommets comme visités → boucle infinie
Confondre BFS (file) et DFS (pile/récursion)
Dijkstra avec poids négatifs → résultats faux
Pour un graphe non orienté, chaque arête apparaît deux fois dans la liste d'adjacence

🏋️ Exercices

IntermédiaireDétection de cycle

Écrire une fonction qui détecte si un graphe non orienté contient un cycle, en utilisant DFS.

✅ Correction

def a_un_cycle(graphe):
    visites = set()
    def dfs(s, parent):
        visites.add(s)
        for v in graphe[s]:
            if v not in visites:
                if dfs(v, s): return True
            elif v != parent:  # visite d'un voisin déjà vu ≠ parent
                return True
        return False
    for s in graphe:
        if s not in visites:
            if dfs(s, None): return True
    return False

📌 Fiche synthèse

REPRÉSENTATIONS

Liste adj : O(V+E) mémoire
Matrice : O(V²) mémoire
Matrice → test arête O(1)
Liste → voisins O(degré)

PARCOURS

BFS : file, plus court chemin
DFS : récursion / pile
Complexité : O(V + E)
Toujours marquer les visités !

DIJKSTRA

Poids positifs uniquement
Utilise un tas-min (heapq)
O((V+E) log V)
Plus court depuis source

🧠 QCM

Choisissez le nombre de questions et le niveau, puis lancez.

← Arbres POO →