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é.

Un algorithme de recherche du meilleur d'abord qui trouve le chemin le plus court en utilisant des heuristiques. Combine l'algorithme de Dijkstra et la recherche gloutonne du meilleur d'abord en utilisant f(n) = g(n) + h(n). Largement utilisé dans les jeux, la robotique et la navigation GPS pour une recherche de chemin efficace.

Trouve l'arbre couvrant minimal (MST) d'un graphe non orienté pondéré. Utilise une approche gloutonne en triant les arêtes par poids et en les ajoutant si elles ne créent pas de cycle. Emploie Union-Find pour une détection efficace des cycles. Essentiel pour la conception de réseaux et le clustering.

Trouve l'arbre couvrant minimal (MST) en faisant croître un arbre à partir d'un sommet de départ. Ajoute toujours l'arête de poids minimum connectant un sommet dans l'arbre à un sommet à l'extérieur. Utilise une file de priorité pour une sélection efficace des arêtes. Idéal pour les graphes denses.

Ordonne les sommets d'un graphe acyclique dirigé (DAG) de sorte que pour chaque arête u→v, u vienne avant v. Utilise une approche basée sur DFS. Essentiel pour la résolution de dépendances, les systèmes de construction et la planification de cours.

Algorithme de Google pour classer les pages web par structure de liens. Calcule les scores d'importance de manière itérative.

Aussi connu sous le nom d'algorithme de la 'tortue et du lièvre', cette technique élégante détecte les cycles dans les listes chaînées ou les séquences en utilisant O(1) d'espace. Utilise deux pointeurs se déplaçant à des vitesses différentes - s'il y a un cycle, ils finiront par se rencontrer. Essentiel pour détecter les boucles infinies, analyser les structures de graphes et valider l'intégrité des données.

Algorithme de plus court chemin à source unique qui gère les poids négatifs et détecte les cycles négatifs. Relâche toutes les arêtes V-1 fois pour garantir des distances correctes même avec des poids négatifs. Essentiel pour la détection d'arbitrage de devises, le routage réseau avec des coûts variés et les situations où l'algorithme de Dijkstra échoue. Échange la vitesse contre la flexibilité.

Algorithme de plus courts chemins entre toutes les paires qui calcule les distances entre chaque paire de sommets en temps O(V³). Utilise la programmation dynamique avec une logique centrale élégante de trois lignes. Gère les poids négatifs et fournit la fermeture transitive. Idéal pour les graphes denses, l'analyse de réseau et quand toutes les distances par paires sont nécessaires.

Algorithme glouton qui construit un arbre couvrant minimal en ajoutant des arêtes par ordre de poids croissant, utilisant union-find pour éviter les cycles. Efficace pour les graphes épars avec une complexité temporelle O(E log E). Les applications incluent la conception de réseaux, le clustering, les algorithmes d'approximation et la compréhension des preuves de correction gloutonne.

Algorithme glouton qui fait croître un arbre couvrant minimal en ajoutant répétitivement l'arête la moins chère connectant l'arbre à un nouveau sommet. Utilise une file de priorité pour l'efficacité avec un temps O(E log V). Préféré pour les graphes denses et les applications en temps réel comme la diffusion réseau et la conception de circuits.