Algorithmes de Graphes Essentiels pour les Entretiens de Code

1. Comment Repérer un Problème de Graphe Déguisé

Lors d'un entretien dans une grande entreprise technologique, il est rare de recevoir une consigne qui dit explicitement : "Voici un graphe orienté acyclique, veuillez le parcourir". Au lieu de cela, les problèmes de graphes sont généralement déguisés en scénarios du monde réel ou en énigmes basées sur des grilles.

Vous devriez immédiatement commencer à penser aux algorithmes de graphes si la description du problème implique l'un des thèmes suivants :

• Connexions : "Trouvez des personnes qui sont des amis d'amis", "Déterminez s'il y a un vol entre la Ville A et la Ville B".
• Dépendances : "Vous avez une liste de tâches et de prérequis, dans quel ordre devez-vous les accomplir ?" ou "Compilez un projet avec des dépendances".
• Grilles et Labyrinthes : "Trouvez le chemin le plus court pour sortir de ce labyrinthe en tableau 2D", "Comptez le nombre d'îles dans une grille".
• Transformations : "Changez un mot en un autre mot en modifiant une seule lettre à la fois (Word Ladder)".

Une fois que vous avez identifié qu'il s'agit d'un problème de graphe, votre prochaine étape consiste à trouver la meilleure représentation. Les Listes d'Adjacence (en utilisant des Hash Maps ou des listes de listes) sont généralement le meilleur choix pour les entretiens car elles sont efficaces en mémoire et rapides à itérer. Les grilles (tableaux 2D) agissent comme des graphes implicites, où chaque cellule est un nœud et ses cellules adjacentes sont ses arêtes.

2. Modèle 1 : Recherche en Largeur (BFS) pour les Plus Courts Chemins

La Recherche en Largeur (Breadth-First Search) est votre algorithme de prédilection chaque fois qu'un problème demande le "plus court chemin" ou le "nombre minimum d'étapes" dans un graphe non pondéré.

BFS explore le graphe niveau par niveau, rayonnant vers l'extérieur comme des ondulations dans un étang. Parce qu'il explore tous les nœuds à une distance de 1 avant d'explorer tout nœud à une distance de 2, la première fois qu'il atteint le nœud de destination, il est garanti d'avoir trouvé le chemin le plus court.

Mots-clés d'Identification :

Plus court chemin, étapes minimales, le plus proche, parcours par niveau.

Modèle d'Implémentation (Python) :

BFS nécessite toujours une File (Queue) (structure de données FIFO) et un Ensemble de Visités (Visited Set) pour éviter les boucles infinies.

from collections import deque

def bfs_shortest_path(graph, start, target):
    queue = deque([(start, 0)]) # (current_node, distance)
    visited = set([start])
    
    while queue:
        node, distance = queue.popleft()
        
        if node == target:
            return distance
            
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
                
    return -1 # Chemin non trouvé

Problèmes Classiques sur LeetCode : Word Ladder, Shortest Path in Binary Matrix, Rotting Oranges.

3. Modèle 2 : Recherche en Profondeur (DFS) pour la Connectivité

La Recherche en Profondeur (Depth-First Search) explore un graphe en allant aussi loin que possible sur un chemin avant de revenir sur ses pas (backtracking). Bien qu'il soit rarement utilisé pour trouver le chemin le plus court, il est incroyablement efficace pour explorer la structure entière d'un graphe, trouver des composantes, ou vérifier si un chemin existe tout court.

DFS est très apprécié lors des entretiens car il peut être implémenté de manière très concise en utilisant la récursivité.

Mots-clés d'Identification :

Connectivité, accessibilité, tous les chemins, exploration de régions, backtracking, recherche profonde.

Modèle d'Implémentation (Python) :

DFS nécessite une Pile (Stack) (LIFO), qui est le plus souvent gérée implicitement par la pile d'appels via la récursivité.

def dfs_traverse(graph, start, visited=None):
    if visited is None:
        visited = set()
        
    visited.add(start)
    # Traiter le nœud ici
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_traverse(graph, neighbor, visited)
            
    return visited

Remarque : Si vous faites du backtracking (comme trouver tous les chemins valides ou des permutations), vous devrez retirer le nœud de l'ensemble `visited` après le retour de l'appel récursif.

Problèmes Classiques sur LeetCode : Number of Islands, Clone Graph, Pacific Atlantic Water Flow.

4. Modèle 3 : Tri Topologique pour les Dépendances

Si un problème vous demande de trier des éléments en fonction de prérequis, vous avez besoin du Tri Topologique. Cet algorithme ne fonctionne que sur les Graphes Orientés Acycliques (DAG). S'il y a un cycle (par exemple, la Tâche A nécessite la Tâche B, et la Tâche B nécessite la Tâche A), un tri topologique est impossible.

La façon la plus intuitive de l'implémenter lors d'un entretien est d'utiliser l'Algorithme de Kahn, qui repose sur le calcul du "degré entrant" (in-degree, nombre d'arêtes entrantes) de chaque nœud.

Mots-clés d'Identification :

Prérequis, dépendances, ordonnancement, compilation, résolution.

Modèle d'Implémentation (Python) :

from collections import deque, defaultdict

def topological_sort(num_courses, prerequisites):
    # 1. Construire le Graphe et le tableau des Degrés Entrants
    graph = defaultdict(list)
    in_degree = {i: 0 for i in range(num_courses)}
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
        
    # 2. Trouver tous les nœuds avec un degré entrant de 0 (aucun prérequis)
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    top_order = []
    
    # 3. Traiter la file
    while queue:
        node = queue.popleft()
        top_order.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    # 4. Vérifier s'il y a des cycles
    if len(top_order) == num_courses:
        return top_order
    return [] # Cycle détecté

Problèmes Classiques sur LeetCode : Course Schedule I & II, Alien Dictionary.

5. Modèle 4 : Union-Find pour les Composantes Connexes

Union-Find (Ensembles Disjoints) est une structure de données spécialisée utilisée spécifiquement pour suivre la partition d'un ensemble en sous-ensembles disjoints. Elle répond à deux questions de manière fulgurante (en un temps proche de O(1)) :

1. Le Nœud A et le Nœud B sont-ils dans la même composante ?
2. Pouvons-nous fusionner la composante contenant le Nœud A avec la composante contenant le Nœud B ?

C'est l'outil parfait pour trouver des cycles dans des graphes non orientés ou pour grouper des éléments dynamiquement.

Mots-clés d'Identification :

Composantes connexes, connectivité dynamique, groupement, connexion redondante, fusion d'ensembles.

Modèle d'Implémentation (Python) :

Vous devez mémoriser l'implémentation d'une classe Union-Find, en vous rappelant spécifiquement d'inclure la Compression de Chemin (Path Compression) dans la méthode `find` pour garantir une complexité temporelle optimale.

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size

    def find(self, x):
        # Compression de chemin
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False # Déjà dans le même ensemble (cycle détecté)
            
        # Union par rang
        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        elif self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
            
        return True

Problèmes Classiques sur LeetCode : Redundant Connection, Number of Connected Components in an Undirected Graph, Accounts Merge.

6. Modèle 5 : Dijkstra pour le Plus Court Chemin Pondéré

Si le problème demande le chemin le plus court, mais que les arêtes ont des poids (coûts, temps, distances), le BFS standard échouera. Vous avez besoin de l'algorithme de Dijkstra.

Dijkstra est essentiellement un BFS, mais au lieu d'une File standard, il utilise une File de Priorité (Min-Heap) pour s'assurer que vous explorez toujours le chemin le moins cher disponible ensuite.

Mots-clés d'Identification :

Plus court chemin avec coûts, vol le moins cher, temps minimum, délai de réseau.

Modèle d'Implémentation (Python) :

import heapq

def dijkstra(graph, start, target):
    # La file de priorité stocke des tuples (total_cost, node)
    pq = [(0, start)]
    # Dictionnaire pour garder une trace du coût minimum pour atteindre chaque nœud
    min_cost = {start: 0}
    
    while pq:
        current_cost, node = heapq.heappop(pq)
        
        # Si nous avons atteint la cible, c'est garanti d'être le chemin le plus court
        if node == target:
            return current_cost
            
        # Si nous avons trouvé un chemin plus court précédemment, ignorer cet ancien tuple
        if current_cost > min_cost.get(node, float('inf')):
            continue
            
        for neighbor, weight in graph[node]:
            new_cost = current_cost + weight
            
            # Pousser dans la file uniquement si nous avons trouvé un chemin strictement meilleur
            if new_cost < min_cost.get(neighbor, float('inf')):
                min_cost[neighbor] = new_cost
                heapq.heappush(pq, (new_cost, neighbor))
                
    return -1

Problèmes Classiques sur LeetCode : Network Delay Time, Cheapest Flights Within K Stops (Remarque : Bellman-Ford est également bon pour celui-ci), Path With Maximum Probability.