Graphes et parcours 🌐

Un graphe est une structure qui modélise des relations entre des entités. Réseaux sociaux, cartes GPS, Internet, dépendances logicielles — tout ça, ce sont des graphes !

1. Représentation des graphes 📐

Deux façons de représenter un graphe en mémoire :

Liste d'adjacence

Chaque nœud a une liste de ses voisins. Économique pour les graphes creux (peu de connexions).

Exécution pas à pas
pseudo
1/4
▶️STRUCTURE Graphe
STRUCTURE GrapheLe programme exécute cette action, puis passe à la suivante.
Le programme exécute cette instruction, puis passe à la suivante.


# Liste d'adjacence : chaque nœud → liste de ses voisins
graph = {
    "A": ["B", "C"],     # A est connecté à B et C
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

Matrice d'adjacence

Tableau 2D où matrice[i][j] = 1 s'il y a une arête entre i et j. Accès O(1) mais mémoire O(V²).

💡 Quand utiliser quoi ?

Liste d'adjacence : la plupart des cas (graphes creux, parcours BFS/DFS)

Matrice d'adjacence : petits graphes denses, quand l'accès direct est critique

2. Parcours en largeur (BFS) — Breadth-First Search 🏗️

Principe : On explore niveau par niveau, comme une tache d'huile. On utilise une file (FIFO).

Exécution pas à pas
pseudo
1/18
🧩FONCTION bfs(graphe, départ)
FONCTION bfs(graphe, départ)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "bfs(graphe, départ)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.


from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            queue.extend(graph[node])

bfs(graph, "A")  # A B C D E F (ordre par niveau)

Ordre de visite : A → B, C → D, E, F

🔍 Utilisations :

Plus court chemin dans un graphe non pondéré

Nombre d'îles (grille binaire)

Navigation en couches (réseau social : "amis d'amis")

3. Parcours en profondeur (DFS) — Depth-First Search 🕳️

Principe : On explore un chemin jusqu'au bout avant de revenir en arrière (backtracking). On utilise une pile (LIFO) — ou la récursion.

Exécution pas à pas
pseudo
1/10
🧩FONCTION dfs(graphe, nœud, visités ← {})
FONCTION dfs(graphe, nœud, visités ← {})Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "dfs(graphe, nœud, visités ← {})". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.


def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

dfs(graph, "A")  # A B D E F C (ordre en profondeur)

Ordre de visite : A → B → D → E → F → C (on va tout droit jusqu'au bout, puis on remonte)

🔍 Utilisations :

Détection de cycle

Tri topologique (ordonnancement de tâches)

Backtracking (sudoku, labyrinthe)

4. Exercice : Détection de cycle dans un graphe 🔄

Exécution pas à pas
pseudo
1/28
🧩FONCTION détecter_cycle(graphe)
FONCTION détecter_cycle(graphe)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "détecter_cycle(graphe)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.


def detect_cycle(graph):
    visited = set()
    rec_stack = set()

    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:  # Retour vers un nœud actif = cycle !
                return True
        rec_stack.discard(node)
        return False

    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    return False

5. Exercice : Nombre d'îles 🏝️

Compter le nombre d'îles dans une grille binaire (1 = terre, 0 = eau). Chaque île est un groupe de 1 adjacents (horizontal/vertical).

Exécution pas à pas
pseudo
1/25
🧩FONCTION nombre_îles(grille)
FONCTION nombre_îles(grille)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "nombre_îles(grille)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.


def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or grid[r][c] == "0"):
            return
        grid[r][c] = "0"  # On coule la case
        dfs(r + 1, c)     # Explorer dans les 4 directions
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                dfs(r, c)  # Couler toute l'île
    return count

grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]
print(num_islands(grid))  # 3 îles

6. Plus court chemin : Dijkstra 🗺️

Trouve le plus court chemin pondéré (arêtes avec poids) entre un départ et tous les autres nœuds.

Exécution pas à pas
pseudo
1/24
🧩FONCTION dijkstra(graphe, départ)
FONCTION dijkstra(graphe, départ)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "dijkstra(graphe, départ)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.


import heapq

def dijkstra(graph, start):
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # File de priorité : (distance, nœud)

    while pq:
        dist, node = heapq.heappop(pq)  # Nœud avec la plus petite distance
        if dist > distances[node]:
            continue  # On a déjà trouvé un meilleur chemin
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return distances

graph_pond = {
    "A": [("B", 4), ("C", 2)],
    "B": [("D", 5)],
    "C": [("D", 1)],
    "D": []
}
print(dijkstra(graph_pond, "A"))  # {'A': 0, 'B': 4, 'C': 2, 'D': 3}

Comment Dijkstra trouve le chemin le plus court :

Depuis A : B=4 (direct), C=2 (direct)

Le plus proche est C (2). Depuis C, on peut aller à D en 2+1=3

Le prochain plus proche est B (4). Depuis B, D passe à 4+5=9 (pas mieux que 3)

Résultat : A→C→D = 3 ✅

Exercices récapitulatifs 🎯

Implémente BFS et DFS itératifs et récursifs
Détecte un cycle dans un graphe orienté
Compte le nombre d'îles dans une grille binaire
Dijkstra : trouve le plus court chemin dans un graphe pondéré
Floyd : détection de cycle dans une liste chaînée
Bonus : tri topologique d'un graphe orienté acyclique (DAG)

Exécution pas à pas

0/10

État de la mémoire

5 variables

Variable

Valeur

Type

Addr.

dist[A]

int

0x4200

dist[B]

int

0x4204

dist[C]

int

0x4208

dist[D]

int

0x420C

précédent[D]

str

0x4210

Aucune variable active

dist[A]0x4200

int

dist[B]0x4204

int

dist[C]0x4208

int

dist[D]0x420C

int

précédent[D]0x4210

str

⚡ Simulateur — BFS — Parcours en largeur

Étape 1/24

📝 Pseudo-code

1FONCTION bfs(graphe, depart)

2 file = [depart]

3 visite = {depart}

4 TANT QUE file NON VIDE FAIRE

5 noeud = file.defiler()

6 POUR voisin DANS graphe[noeud] FAIRE

7 SI voisin PAS DANS visite ALORS

8 visite.ajouter(voisin)

9 file.enfiler(voisin)

10 FIN SI

11 FIN POUR

12 FIN TANT QUE

13FIN FONCTION

🌐 Graphe BFS

En cours Examiné En file Visité Non visité

📋 File d'attente

vide

✅ Visités

aucun

💡 BFS

Parcourt le graphe niveau par niveau
Utilise une file (FIFO) pour les nœuds à visiter
Complexité : O(V + E) où V=nœuds, E=arêtes
Utile pour trouver le plus court chemin

BFS : exploration niveau par niveau. Graphe non orienté.