# Implementing Randomized Kruskal’s Algorithm

Learn to implement Kruskal's algorithm in Ruby.

## Kruskal's algorithm in mazes

To implement Kruskal’s algorithm in our mazes, we’re going to create a new class, `State`

, to represent the **state of the algorithm**—the collection of information that it will use internally. Once we’ve got this `State`

class written, the rest of Kruskal’s algorithm becomes almost trivial to implement.

Kruskal’s algorithm initially requires that each cell be associated with a unique set. This suggests that, at a minimum, our `State`

class is going to need to track that association. We’ll need a way to query the set that a particular cell belongs to, as well as the list of cells that belong to a given set. Also, the algorithm wants to select random pairs of neighboring cells on each iteration, so we could probably help things along by keeping a list of those cell pairs. Let's get things started by creating a new class called `Kruskals`

.

### The `Kruskals`

class

Get hands-on with 1200+ tech skills courses.