Solution: Modified Prim's Algorithm

class ModifiedPrims
  def self.on(grid, start: grid.random_cell)
    visited = Set.new
    frontier = Set.new([ start ])
    while frontier.any?
      cell = frontier.entries.sample
      frontier.delete(cell)
      visited.add(cell)
      in_neighbors, out_neighbors = cell.neighbors.partition { |n| visited.include?(n) }
      in_neighbor = in_neighbors.sample 
      cell.link(in_neighbor) if in_neighbor
      frontier += out_neighbors 
    end
    grid
  end
end