0Pricing
Coding Interview Prep · Leçon

Représentations des graphes et préparation des parcours

Construisez des graphes orientés et non orientés avec des listes d’adjacence, initialisez BFS avec une deque et DFS avec une pile ou la récursivité, en assurant le suivi des sommets visités.

Représentations des graphes et préparation des parcours est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu’est-ce qu’un graphe ?

Un graphe est un ensemble de nœuds (sommets) reliés par des arêtes. Contrairement aux arbres, les graphes peuvent contenir des cycles, plusieurs chemins entre les nœuds et des composantes déconnectées. Les graphes modélisent des systèmes réels tels que les réseaux sociaux, les cartes routières, les arbres de dépendances et les liens entre pages web. Presque tout entretien d’algorithmique ou de conception de systèmes portant sur un système non trivial aborde les graphes — maîtriser leur représentation et leur parcours est essentiel.

# Graph terminology:
# - V: set of vertices (nodes)
# - E: set of edges
# - Directed graph: edges have direction (A -> B but not B -> A)
# - Undirected graph: edges are bidirectional
# - Weighted graph: edges have costs/weights
# - Cyclic: contains at least one cycle
# - Acyclic: no cycles (DAG = Directed Acyclic Graph)
# - Connected: every node reachable from every other
# - Disconnected: multiple isolated components
print('Graph: nodes + edges, directed/undirected, weighted/unweighted')

Représentation par liste d’adjacence

Une liste d’adjacence stocke la liste des voisins de chaque nœud. En Python, utilisez un dict associant chaque nœud à une liste de nœuds adjacents. Il s’agit de la représentation la plus courante dans les problèmes d’entretien technique : espace O(V + E) (efficace pour les graphes clairsemés), O(degré) pour parcourir les voisins et O(1) en moyenne pour vérifier l’adjacence avec une variante utilisant un ensemble de hachage. La plupart des problèmes de graphes de LeetCode utilisent ce format.

from collections import defaultdict

# Build an undirected graph
def build_undirected(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # both directions
    return graph

edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]
graph = build_undirected(edges)
print(dict(graph))
# {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2,4], 4:[3]}

# Directed graph: only one direction
def build_directed(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)  # only u -> v
    return graph

Représentation par matrice d’adjacence

Une matrice d’adjacence est un tableau 2D V×V dans lequel matrix[i][j] = 1 (ou le poids de l’arête) s’il existe une arête de i vers j, et 0 sinon. Elle permet de rechercher une arête en O(1), mais utilise un espace O(V²) quel que soit le nombre d’arêtes — ce qui est inefficace pour les graphes clairsemés. Elle est préférable lorsque le graphe est dense (avec de nombreuses arêtes) ou lorsque les vérifications rapides de l’existence d’une arête sont essentielles, comme dans le calcul des plus courts chemins entre toutes les paires avec Floyd-Warshall.

# Adjacency matrix for 5 nodes
V = 5
matrix = [[0] * V for _ in range(V)]

edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1  # undirected

# Print the matrix:
for row in matrix:
    print(row)
# Neighbour check: O(1)
print('Edge 0-2:', bool(matrix[0][2]))  # True
print('Edge 0-4:', bool(matrix[0][4]))  # False

# Space: O(V^2) vs adjacency list O(V+E)
# Dense graph: matrix often better; sparse: list better

Représentation par liste d’arêtes

Une liste d’arêtes est la représentation la plus simple : il s’agit simplement d’une liste de tuples (source, destination), éventuellement accompagnés de poids. Elle utilise un espace O(E) et permet de parcourir facilement toutes les arêtes. En revanche, trouver les voisins d’un nœud nécessite de parcourir toutes les arêtes : O(E). Les listes d’arêtes sont utilisées dans les algorithmes de graphes qui parcourent exactement toutes les arêtes, comme Bellman-Ford (relaxation de toutes les arêtes n-1 fois) et l’algorithme de Kruskal pour trouver l’arbre couvrant de poids minimal.

# Weighted edge list: (source, destination, weight)
edge_list = [
    (0, 1, 4),
    (0, 2, 1),
    (1, 3, 1),
    (2, 3, 5),
    (3, 4, 3)
]

# Useful for:
# Bellman-Ford: iterate all edges n-1 times
# Kruskal's MST: sort by weight then union-find

# Sort by weight for Kruskal:
edge_list_sorted = sorted(edge_list, key=lambda e: e[2])
print('Sorted by weight:', edge_list_sorted)

# Finding neighbours: O(E) scan -- inefficient for traversal
node_0_neighbors = [v for u, v, w in edge_list if u == 0]
print('Node 0 neighbors:', node_0_neighbors)

Configuration de BFS : file et ensemble des nœuds visités

BFS (parcours en largeur) explore un graphe niveau par niveau à l’aide d’une file. L’élément essentiel est un ensemble des nœuds visités pour éviter de revisiter les nœuds dans les graphes cycliques. Sans cet ensemble, BFS sur un graphe cyclique tournerait indéfiniment. La configuration standard consiste à initialiser la file avec le nœud source, à le marquer comme visité, puis à retirer, traiter et ajouter à la file de manière répétée les voisins qui n’ont pas encore été visités.

from collections import deque

def bfs(graph, start):
    visited = {start}        # mark source as visited
    queue = deque([start])   # initialise queue
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)     # mark BEFORE enqueue
                queue.append(neighbour)
    return order

from collections import defaultdict
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,3),(2,3),(3,4)]:
    graph[u].append(v); graph[v].append(u)

print(bfs(graph, 0))  # [0, 1, 2, 3, 4]

Configuration de DFS : pile ou récursion

DFS (parcours en profondeur) explore chaque branche aussi loin que possible avant de revenir en arrière. Implémentez-le de manière récursive (à l’aide de la pile d’appels) ou itérative (à l’aide d’une pile explicite). Les deux approches nécessitent un ensemble des nœuds visités pour les graphes cycliques. La version itérative ajoute les voisins dans l’ordre inverse afin de reproduire l’ordre de parcours du DFS récursif, même si l’ordre d’exploration peut varier entre les deux implémentations.

def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None: visited = set(); order = []
    visited.add(node)
    order.append(node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited, order)
    return order

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        order.append(node)
        for neighbour in reversed(graph[node]):  # reverse for same order as recursive
            if neighbour not in visited:
                stack.append(neighbour)
    return order

print('Recursive DFS:', dfs_recursive(graph, 0))
print('Iterative DFS:', dfs_iterative(graph, 0))

Quand utiliser BFS ou DFS

Choisissez BFS lorsque vous avez besoin du plus court chemin (avec le moins d’arêtes) dans un graphe non pondéré ou lorsque vous devez traiter les nœuds niveau par niveau. Choisissez DFS lorsque vous devez explorer tous les nœuds accessibles, détecter les cycles, trouver les composantes connexes, effectuer un tri topologique ou énumérer tous les chemins. En pratique : BFS pour « plus court / nombre minimal de sauts », DFS pour « existence / accessibilité / énumération ».

# BFS use cases:
# - Shortest path in unweighted graph (fewest edges)
# - Level-order traversal
# - Word ladder (minimum transformations)
# - Clone graph

# DFS use cases:
# - Connected components (flood fill)
# - Cycle detection
# - Topological sort
# - All paths between two nodes
# - Maze solving (any path)
# - N-queens, Sudoku (backtracking)

# Both: O(V + E) time, O(V) space for visited
print('BFS: shortest hops | DFS: existence and enumeration')

Graphes issus des formats d’entrée de LeetCode

Les problèmes de graphes de LeetCode utilisent différents formats d’entrée. Liste d’arêtes : [[0,1],[0,2]] — construisez une liste d’adjacence. Liste d’adjacence indexée : graph[i] est la liste des voisins de i. Grille/matrice : un tableau 2D m×n dans lequel les cellules sont les nœuds et les cellules adjacentes (haut/bas/gauche/droite) sont les voisines. Node avec enfants : des classes personnalisées comme Node(val, neighbors). Identifiez ces formats et convertissez-les en liste d’adjacence dès la première étape.

# Format 1: edge list -> adjacency list
def edges_to_adj(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph

# Format 2: 2D grid -> adjacency (implicit)
# Neighbours of (r, c): (r-1,c), (r+1,c), (r,c-1), (r,c+1)
DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
def grid_neighbours(grid, r, c):
    rows, cols = len(grid), len(grid[0])
    return [(r+dr, c+dc) for dr, dc in DIRS
            if 0 <= r+dr < rows and 0 <= c+dc < cols]

grid = [[1,1,0],[0,1,1],[1,0,0]]
print('Neighbours of (0,0):', grid_neighbours(grid, 0, 0))
print('Neighbours of (1,1):', grid_neighbours(grid, 1, 1))

Marquage des cellules visitées dans les grilles

Pour les problèmes de grille, vous pouvez suivre les cellules visitées de deux façons. Option A : utilisez un ensemble visited séparé de tuples (row, col) — espace supplémentaire O(m*n). Option B : modifiez la grille sur place en marquant les cellules visitées avec une valeur sentinelle (par exemple '#' ou 2), puis restaurez-les si nécessaire. L’approche sur place utilise un espace supplémentaire O(1) et est courante pour le remplissage par propagation et les problèmes de comptage des îles.

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:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '#'  # mark as visited (in-place)
        dfs(r+1, c); 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':
                dfs(r, c)
                count += 1
    return count

grid = [['1','1','0','0'],
        ['1','1','0','0'],
        ['0','0','1','0'],
        ['0','0','0','1']]
print(num_islands(grid))  # 3

Initialisation de BFS avec plusieurs sources

Le BFS multisource démarre simultanément à partir de plusieurs nœuds en initialisant la file avec tous les nœuds sources marqués comme visités. Cette approche est utilisée dans des problèmes comme « distance jusqu’au 0 le plus proche », « oranges pourries » et « murs et portes », lorsque vous recherchez la distance minimale depuis n’importe lequel des nœuds sources. Le BFS multisource s’exécute en O(V + E), comme celui à source unique, car chaque nœud n’est toujours visité qu’une seule fois au maximum.

from collections import deque

def rotting_oranges(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Multi-source: all rotten oranges start at time=0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, time)
            elif grid[r][c] == 1:
                fresh += 1
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    time = 0
    while queue:
        r, c, t = queue.popleft()
        for dr, dc in dirs:
            nr, nc = r+dr, c+dc
            if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==1:
                grid[nr][nc] = 2  # mark rotten
                fresh -= 1
                queue.append((nr, nc, t+1))
                time = t + 1
    return time if fresh == 0 else -1

print(rotting_oranges([[2,1,1],[1,1,0],[0,1,1]]))  # 4

Densité du graphe et choix de la représentation

Le choix entre une liste d’adjacence et une matrice dépend de la densité du graphe — le rapport E/V². Un graphe clairsemé (E << V²) bénéficie des listes d’adjacence : espace O(V+E), contre O(V²) pour une matrice. Un graphe dense (E ≈ V²) bénéficie des matrices d’adjacence : recherche d’une arête en O(1), contre O(degré) pour les listes. Pour les problèmes d’entretien technique, les listes d’adjacence constituent presque toujours le bon choix, car la plupart des problèmes concernent des graphes clairsemés.

# Graph density comparison:
# Sparse: social network (V=1B users, avg 200 friends)
#   E = 200 * 1B = 200B << V^2 = 10^18 -> adjacency list
# Dense: complete graph (every node connected to every other)
#   E = V*(V-1)/2 ≈ V^2 -> adjacency matrix

# Interview rule of thumb:
# - Default to adjacency list (defaultdict(list))
# - Use matrix only when asked about dense graph or O(1) edge lookup
# - Grid problems: use implicit adjacency (4-directional neighbours)

print('Sparse graph (E << V^2): use adjacency list')
print('Dense graph (E ~ V^2): consider adjacency matrix')

Vérification rapide

Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation abordés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris : les trois représentations des graphes (liste d’adjacence, matrice, liste d’arêtes) et le moment de choisir chacune d’elles, la configuration de BFS et DFS avec des ensembles de nœuds visités pour éviter les boucles infinies dans les graphes cycliques, ainsi que des méthodes pratiques comme le marquage sur place de la grille et le BFS multisource. Ensuite, vous appliquerez BFS pour trouver les plus courts chemins et effectuer un parcours par niveaux.

Questions Fréquemment Posées

La leçon « Représentations des graphes et préparation des parcours » est-elle gratuite ?

Oui — le texte complet de « Représentations des graphes et préparation des parcours » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Représentations des graphes et préparation des parcours » ?

Construisez des graphes orientés et non orientés avec des listes d’adjacence, initialisez BFS avec une deque et DFS avec une pile ou la récursivité, en assurant le suivi des sommets visités. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.

Combien de temps prend la leçon « Représentations des graphes et préparation des parcours » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Représentations des graphes et préparation des parcours
  2. BFS : plus court chemin et parcours par niveaux
  3. DFS : composantes connexes et remplissage
  4. Détection de cycles dans les graphes orientés et non orientés
← Retour à Coding Interview Prep