Algorithme de Hoshen-Kopelman
From Wikipedia, the free encyclopedia
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.
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)[1].
Description
L'algorithme est une application de la structure de données union-find[1].
