Liste des algorithmes de la théorie des graphes

Cette page présente une liste non exhaustive des principaux algorithmes de la théorie des graphes.

Algorithmes de parcours d'un graphe

• Algorithme de parcours en largeur (ou BFS : Breadth First Search)
• Algorithme de parcours en profondeur (ou DFS : Depth First Search)
• Algorithme de parcours en largeur lexicographique (ou Lex-BFS)

Algorithmes de plus courts chemins (PCC)

• Algorithme de Dijkstra
• Algorithme de Dantzig
• Algorithme de Bellman-Ford-Moore
• Algorithme de Floyd-Warshall
• Algorithme de Johnson
• Algorithme A*

Algorithmes d'arbres couvrants de poids minimum

• Algorithme de Kruskal
• Algorithme de Prim
• Algorithme de Borůvka

Lemme de Minty

• Lemme de Minty

Algorithmes pour les flots maximums

• Algorithme de Ford-Fulkerson

Algorithmes pour les flots à coût minimum

• Algorithme de Busacker et Gowen
• Algorithme de Klein

Algorithmes pour les flots compatibles

• Algorithme de recherche de flots compatibles

Algorithmes de coloration

(voir coloration de graphe)

Algorithmes divers

• Algorithme du plus proche voisin
• Algorithmes de connexité
• Algorithme de détermination des composantes biconnexes
• Algorithmes de forte connexité
• Algorithme de Christofides pour l'approximation du problème du voyageur de commerce métrique
• Algorithme de Karger pour la coupe minimum (probabiliste)