Metraipolis › archive › dc_a2de954fe362
Algorithmes de connexité basés sur des pointeurs — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Algorithmes_de_connexit%C3%A9_bas%C3%A9s_sur_des_pointeurs
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-17T11:57:14.226Z
- SHA-256 of the archived text
3e398bd6949974dc45003a24ec2bae3cdaad0f9505f7afa58bbcdd79bd29e486- Stable URL of this page
https://metraipolis.com/documento/dc_a2de954fe362
How to cite
Algorithmes de connexité basés sur des pointeurs — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithmes_de_connexit%C3%A9_bas%C3%A9s_sur_des_pointeurs (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_a2de954fe362 (Metraipolis archive dc_a2de954fe362, sha256 3e398bd6949974dc45003a24ec2bae3cdaad0f9505f7afa58bbcdd79bd29e486)
BibTeX
@misc{dca2de954fe362,
title = {Algorithmes de connexité basés sur des pointeurs — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Algorithmes_de_connexit%C3%A9_bas%C3%A9s_sur_des_pointeurs},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_a2de954fe362; sha256 3e398bd6949974dc45003a24ec2bae3cdaad0f9505f7afa58bbcdd79bd29e486},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithmes_de_connexit%C3%A9_bas%C3%A9s_sur_des_pointeurs. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Les algorithmes de connexité permettent de déterminer rapidement si deux sommets d'un graphe non orienté sont reliés par un chemin ou non, en créant un tableau de pointeurs qui implémente en fait une forêt d'arbres. Chaque arbre créé par l'algorithme correspond à une composante connexe du graphe : ainsi, deux sommets seront reliés par un chemin du graphe si et seulement s'ils appartiennent au même arbre. La vérification se résume à la comparaison des racines des arbres respectifs. Dans le cas d'un graphe fixé à l'avance, cet algorithme est moins efficace que l'algorithme de parcours en largeur et l'algorithme de parcours en profondeur, qui permettent de répondre à ce type de requête en temps constant après un prétraitement linéaire. Cependant, il est utile dans le cas d'un graphe construit de façon incrémentale. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico). Fonte: Wikipedia in francese, voce «Algorithmes de connexité basés sur des pointeurs» — https://fr.wikipedia.org/wiki/Algorithmes_de_connexit%C3%A9_bas%C3%A9s_sur_des_pointeurs Wikidata Q2835883 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2835883 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithmes_de_connexit%C3%A9_bas%C3%A9s_sur_des_pointeurs?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 182938743, consultata il 2026-10-17T11:27:34.362Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 661b226c8b56698205631841f93b3d8144d345259598406910ca728f6a9b6df0