Liste des algorithmes de la théorie des graphes

Un article de Wikipédia, l'encyclopédie libre.

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

Sommaire 1 Algorithmes de parcours d'un graphe 2 Algorithmes de Plus Courts Chemins (PCC) 3 Algorithmes d'arbres couvrants de poids minimum 4 Algorithmes de construction d'une forêt maximale 5 Lemme de Minty 6 Algorithmes pour les flots maximums 7 Algorithmes pour les flots à coût minimum 8 Algorithmes pour les flots compatibles 9 Algorithmes de coloration 10 Algorithmes divers

[modifier] 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)

[modifier] Algorithmes de Plus Courts Chemins (PCC)

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

[modifier] Algorithmes d'arbres couvrants de poids minimum

• Algorithme de Kruskal
• Algorithme de Prim

[modifier] Algorithmes de construction d'une forêt maximale

• Algorithme de construction d'une forêt maximale

[modifier] Lemme de Minty

• Lemme de Minty

[modifier] Algorithmes pour les flots maximums

• Algorithme de Ford-Fulkerson
• Algorithme de Roy

[modifier] Algorithmes pour les flots à coût minimum

• Algorithme de Busacker-Gowen
• Algorithme de Klein

[modifier] Algorithmes pour les flots compatibles

• Algorithme de recherche de flots compatibles

[modifier] Algorithmes de coloration

(voir coloration de graphe)

[modifier] 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