Metraipolis › archive › dc_3152b2fd92e1

Algorithme de Kruskal — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T18:04:28.337Z
SHA-256 of the archived text
ac82504811683c825efa079906b0e8eb559631303424f2894350c630c7e051fc
Stable URL of this page
https://metraipolis.com/documento/dc_3152b2fd92e1

How to cite

Algorithme de Kruskal — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_3152b2fd92e1 (Metraipolis archive dc_3152b2fd92e1, sha256 ac82504811683c825efa079906b0e8eb559631303424f2894350c630c7e051fc)
BibTeX
@misc{dc3152b2fd92e1,
  title = {Algorithme de Kruskal — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_3152b2fd92e1; sha256 ac82504811683c825efa079906b0e8eb559631303424f2894350c630c7e051fc},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «théorie des graphes»).
Fonte: Wikipedia in francese, voce «Algorithme de Kruskal» — https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal
Wikidata Q797860 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q797860
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 238717743, consultata il 2026-10-15T17:15:12.433Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 6dd8f82d992f61a4345851823aa34fcd86f67f59ab9b6fced5e9f4a08ace505a