Algorithme de Kruskal

En informatique, l'algorithme de Kruskal est un algorithme de recherche d'arbre couvrant minimum (ACM) dans un graphe connexe non-orienté et pondéré. Dans un graphe non connexe, il construit une forêt dont chaque arbre est un arbre couvrant minimum d'une composante connexe. Un arbre couvrant T {\displaystyle T} d'un graphe G {\displaystyle G} est un arbre (graphe acyclique) tel que l'ensemble des sommets de T {\displaystyle T} est le même que celui de G {\displaystyle G} : l'arbre « couvre » le graphe G {\displaystyle G} . Pour un graphe pondéré, un arbre couvrant minimal minimise la somme du poids des arêtes. L'algorithme de Kruskal est un algorithme glouton, c'est-à-dire qu'à chaque étape il prend l’arête de poids minimum ne formant pas un cycle. Le premier algorithme s'intéressant à la recherche d’un arbre couvrant minimal est publié par Otakar Borůvka en 1926. L’algorithme de Kruskal est publié par Joseph Kruskal en 1956, puis est redécouvert par H. Loberman et A. Weinberger en 1957.