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-Moore
• Algorithme de Ford
• Algorithme de Floyd-Warshall
• Algorithme de Ford-Bellman
• Algorithme A*

Algorithmes d'arbres couvrants de poids minimum

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

Algorithmes de construction d'une forêt maximale

• Algorithme de construction d'une forêt maximale

Lemme de Minty

• Lemme de Minty

Algorithmes pour les flots maximums

• Algorithme de Ford-Fulkerson
• Algorithme de Roy

Algorithmes pour les flots à coût minimum

• Algorithme de Busacker-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é

• Portail des mathématiques