Graphes : BFS et DFS
AvancéUn graphe modélise des relations (réseau, carte, dépendances) : BFS trouve le plus court chemin non pondéré, DFS explore en profondeur.
Un graphe est un ensemble de sommets (V) reliés par des arêtes (E), orientées ou non. On le stocke en liste d'adjacence (voisins[u] = liste des sommets voisins de u, mémoire O(V + E)) ; la matrice d'adjacence coûte O(V²) et ne convient qu'aux graphes denses.
Une grille est un graphe implicite : chaque case a jusqu'à 4 voisins (haut, bas, gauche, droite). C'est la forme la plus fréquente en entretien.
| Parcours | Structure | Sert à | Complexité |
|---|---|---|---|
| BFS (largeur) | File | Plus court chemin sans poids, parcours par niveaux | O(V + E) |
| DFS (profondeur) | Pile ou récursion | Composantes connexes, détection de cycle, explorer tous les chemins | O(V + E) |
BFS : plus court chemin dans une grille#
0 = libre, 1 = mur. On part de la case en haut à gauche ; on renvoie le nombre de pas jusqu'à la case en bas à droite, ou -1.
function shortestPath(grid: number[][]): number {
const rows = grid.length;
const cols = grid[0].length;
if (grid[0][0] === 1 || grid[rows - 1][cols - 1] === 1) return -1;
const visited = grid.map((row) => row.map(() => false));
let queue: [number, number][] = [[0, 0]];
visited[0][0] = true;
let steps = 0;
while (queue.length) {
const next: [number, number][] = [];
for (const [r, c] of queue) {
if (r === rows - 1 && c === cols - 1) return steps;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr;
const nc = c + dc;
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid[nr][nc] === 1 || visited[nr][nc]) continue;
visited[nr][nc] = true; // marquer à l'ajout, pas au retrait
next.push([nr, nc]);
}
}
queue = next; // niveau suivant
steps++;
}
return -1;
}
DFS : compter les îlots#
Chaque case 1 non visitée démarre une nouvelle île ; le DFS « inonde » toutes les cases connectées.
function countIslands(grid: number[][]): number {
const rows = grid.length;
const cols = grid[0].length;
const seen = grid.map((row) => row.map(() => false));
function flood(r: number, c: number): void {
if (r < 0 || c < 0 || r >= rows || c >= cols) return;
if (grid[r][c] === 0 || seen[r][c]) return;
seen[r][c] = true;
flood(r + 1, c);
flood(r - 1, c);
flood(r, c + 1);
flood(r, c - 1);
}
let islands = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 1 && !seen[r][c]) {
islands++;
flood(r, c);
}
}
}
return islands;
}
Piège : marquez un sommet comme visité quand vous l'ajoutez à la file (BFS), pas quand vous le retirez : sinon il peut être ajouté plusieurs fois. Sur de très grandes grilles, un DFS récursif peut faire déborder la pile d'appels : passez à une pile explicite.