L'Atelier Monstre

Problème 1 : Emplacement optimal de l'hôpital Description du problème Considérons un arbre binaire, comme illustré ci-dessous : Les valeurs dans les nœuds représentent la population des résidents, et les numéros à côté sont les identifiants des nœuds. L'objectif est de construire un hôpital sur un nœud de sorte que la somme des distances parcou ...

Cet article présente une approche pour identifier et lister toutes les composantes connexes d'un graphe non orienté en utilisant deux algorithmes de parcours fondamentaux : le parcours en profondeur (DFS) et le parcours en largeur (BFS). Description du Problème Étant donné un graphe non orienté composé de N sommets et E arêtes, le but est d'énu ...

Introduction au tri topologique : Deux approches principales existent : l'algorithme de Kahn (basé sur BFS) et la méthode DFS. Leur objectif est d'ordonner les nœuds dans un graphe dirigé acyclique (DAG), offrant souvent plusieurs solutions valides. Ces algorithmes identifient également la présence de cycles. Principe de l'algorithme de Kahn (B ...

Problème classique de recherche combinatoire avec test de primalité. #include <iostream> using namespace std; int countPrimes(int val) { if (val < 2) return 0; for (int d = 2; d * d <= val; ++d) { if (val % d == 0) return 0; } return 1; } int totalComb = 0; void generateCombinations(int step, int lastIndex, int ...

11.1 Recherche en profondeur (DFS) 11.1.1 Concepts de base Le DFS (Depth-First Search) est un algorithme récursif qui explore un chemin jusqu'au bout puis fait marche arrière. Gabarit de base void dfs(int etat) { // 1. Condition d'arrêt if (condition satisfaite) { traiter le résultat; return; } // 2. Élagage ...

Les algorithmes de graphes sont fondamentaux pour résoudre de nombreux problèmes en informatique. Cette exploration se concentre sur deux applications classiques : la détection des points d'articulation et des ponts dans les graphes non orientés, et le calcul du chemin critique pour l'ordonnancement de tâches dans les graphes orientés acyclique ...