Algorithme de Hoshen-Kopelman
# Algorithme de Hoshen-Kopelman

L'algorithme de Hoshen-Kopelman est un algorithme de partitionnement (clustering) des cases d'un réseau, autrement dit, il permet de dénombrer les amas d'un type d'objet dans un réseau fini. Il est utilisé pour étudier la percolation.

## Problème algorithmique

Le problème algorithmique résolu par l'algorithme est le suivant : étant donné une grille dont chaque case est soit occupée, soit inoccupée, regrouper les cases occupées en paquets tels que tous les paquets sont formés de cellules contiguës et qu'il y ait le moins de paquets possible (c'est-à-dire que deux paquets ne soient pas contigus).

## Description

L'algorithme est une application de la structure de données union-find.

## Histoire et utilisations

Il a été développé par J. Hoshen et R. Kopelman en 1976 dans le cadre de la détermination de la percolation d'un réseau. Il est toujours utilisé dans ce cadre, de même que l'algorithme de $Leath-Alexandrowicz^,^,.$

