Algorithmes de graphe

Explore un graphe niveau par niveau, visitant tous les sommets à la profondeur actuelle avant d'aller plus profondément. Utilise une file d'attente et est idéal pour trouver les chemins les plus courts dans les graphes non pondérés. Les applications incluent la résolution de labyrinthes, l'analyse de réseaux sociaux et la recherche de connexions entre nœuds.

Explore un graphe en allant aussi profondément que possible le long de chaque chemin avant de revenir en arrière. Implémenté à l'aide d'une pile ou de la récursion, ce qui le rend naturel pour les problèmes récursifs. Utilisé pour la recherche de chemins, la détection de cycles, le tri topologique et la génération de labyrinthes.

Trouve les chemins les plus courts d'un sommet source unique vers tous les autres sommets dans un graphe pondéré. Alimente les systèmes de navigation GPS et les protocoles de routage réseau. Fonctionne efficacement avec des poids d'arêtes non négatifs en utilisant une approche gloutonne avec une file de priorité.

A best-first search algorithm that finds the shortest path using heuristics. Combines Dijkstra's algorithm and greedy best-first search using f(n) = g(n) + h(n). Widely used in games, robotics, and GPS navigation for efficient pathfinding.

Finds the Minimum Spanning Tree (MST) of a weighted undirected graph. Uses a greedy approach by sorting edges by weight and adding them if they don't create a cycle. Employs Union-Find for efficient cycle detection. Essential for network design and clustering.

Finds the Minimum Spanning Tree (MST) by growing a tree from a starting vertex. Always adds the minimum weight edge connecting a vertex in the tree to one outside. Uses a priority queue for efficient edge selection. Ideal for dense graphs.

Orders vertices of a Directed Acyclic Graph (DAG) such that for every edge u→v, u comes before v. Uses DFS-based approach. Essential for dependency resolution, build systems, and course scheduling.

Google's algorithm for ranking web pages by link structure. Computes importance scores iteratively.

Also known as the 'tortoise and hare' algorithm, this elegant technique detects cycles in linked lists or sequences using O(1) space. Uses two pointers moving at different speeds—if there's a cycle, they will eventually meet. Essential for detecting infinite loops, analyzing graph structures, and validating data integrity.

Single-source shortest path algorithm that handles negative weights and detects negative cycles. Relaxes all edges V-1 times to guarantee correct distances even with negative weights. Essential for currency arbitrage detection, network routing with varied costs, and situations where Dijkstra's algorithm fails. Trades speed for flexibility.

All-pairs shortest path algorithm that computes distances between every pair of vertices in O(V³) time. Uses dynamic programming with elegant three-line core logic. Handles negative weights and provides transitive closure. Ideal for dense graphs, network analysis, and when all pairwise distances are needed.

Greedy algorithm that builds a minimum spanning tree by adding edges in order of increasing weight, using union-find to avoid cycles. Efficient for sparse graphs with time complexity O(E log E). Applications include network design, clustering, approximation algorithms, and understanding greedy correctness proofs.

Greedy algorithm that grows a minimum spanning tree by repeatedly adding the cheapest edge connecting the tree to a new vertex. Uses a priority queue for efficiency with O(E log V) time. Preferred for dense graphs and real-time applications like network broadcasting and circuit design.