Accueil › Coding & algorithmique › Graphes et grilles
Graphes et grilles
Récursivité, arbres et graphesavance
Beaucoup d'exercices de graphe se présentent sous forme de grille : chaque case est un nœud, ses voisines sont ses arêtes.
Le motif « compter les îles », à connaître par cœur :
static int compterIles(char[][] grille) {
int n = grille.length, m = grille[0].length, iles = 0;
boolean[][] vu = new boolean[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (grille[i][j] == '1' && !vu[i][j]) {
explorer(grille, vu, i, j); // engloutit toute l'île
iles++; // une de plus
}
return iles;
}
private static final int[][] DIRECTIONS = {{1,0}, {-1,0}, {0,1}, {0,-1}};
private static void explorer(char[][] g, boolean[][] vu, int i, int j) {
if (i < 0 || i >= g.length || j < 0 || j >= g[0].length) return;
if (vu[i][j] || g[i][j] != '1') return;
vu[i][j] = true;
for (int[] d : DIRECTIONS) explorer(g, vu, i + d[0], j + d[1]);
}
Le nombre de lancements du parcours est le nombre de composantes connexes : le même algorithme compte les îles, les groupes d'amis, les régions.
Pour un graphe orienté, la détection de cycle demande trois états :
// 0 = non visité, 1 = en cours, 2 = terminé
static boolean aUnCycle(List<List<Integer>> adj, int[] etat, int n) {
if (etat[n] == 1) return true; // on retombe sur un nœud EN COURS : cycle
if (etat[n] == 2) return false; // déjà exploré, sans cycle
etat[n] = 1;
for (int v : adj.get(n)) if (aUnCycle(adj, etat, v)) return true;
etat[n] = 2;
return false;
}
Un marquage binaire ne suffit pas : réatteindre un nœud terminé n'est pas un cycle.
Les termes à connaître
- Liste d'adjacence
La représentation usuelle d'un graphe :
Map<Noeud, List<Noeud>>ouList<List<Integer>>. Efficace en mémoire dès que le graphe est peu dense.- Matrice d'adjacence
boolean[n][n]: test d'arête en O(1), mais O(n²) en mémoire. Réservée aux petits graphes denses.- Grille comme graphe
Chaque case est un nœud, ses voisines orthogonales (ou diagonales) sont ses arêtes. La plupart des exercices de graphe se présentent en fait sous forme de grille.
- Composante connexe
Un groupe de nœuds tous reliés entre eux. Les compter revient à lancer un parcours depuis chaque nœud non encore visité.
- Détection de cycle
Dans un graphe orienté, un cycle existe si un parcours en profondeur rencontre un nœud en cours de traitement — d'où le marquage à trois états.
- Tri topologique
Un ordre des nœuds tel que chaque arête va de gauche à droite. N'existe que si le graphe orienté est sans cycle. Algorithme de Kahn : file des nœuds de degré entrant nul.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.