Avevo già affrontato l'argomento dei labirinti in un lontano Rompicapo, e ho pensato bene di tornare sull'argomento però da un punto di vista leggermente diverso: gli algoritmi di generazione dei labirinti.
Per generare un labirinto si parte da una griglia di celle, generalmente rettangolare, ma se ne può realizzare una di qualsiasi forma. A questa griglia si associa un percorso in cui i nodi coincidono con il centro di ciascuna cella. Lo scopo del generatore di labirinti è quello di determinare un sottografo in cui sia difficile trovare l'unico percorso che collega due nodi particolari, denominati ingresso e uscita.
Poiché la mappa del labirinto è, di fatto, un albero, ovvero un percorso che unisce un insieme di punti connessi a due a due da una e una sola linea, gli algoritmi di generazione ricadono nel campo della teoria dei grafi. Di tutti i possibili algoritmi (ce ne sono diversi) vi propongo quello basato sull'algoritmo di Kruskal, proposto nel 1956 da Joseph Kruskal(2), fratello di Martin David(1). L'algoritmo si compone di questi passi:
