We developed a new strategy, based on graph theory concepts, to invert gravity data using an ensemble of simple point masses. Our method consisted of a genetic algorithm with elitism to generate a set of possible solutions. Each estimate was associated to a graph to solve the minimum spanning tree (MST) problem. To produce unique and stable estimates, we restricted the position of the point masses by minimizing the statistical variance of the distances of an MST jointly with the data-misfit function during the iterations of the genetic algorithm. Hence, the 3D spatial distribution of the point masses identified the skeleton of homogeneous gravity sources. In addition, our method also gave an estimation of the anomalous mass of the source. So, together with the anomalous mass, the skeleton could aid other 3D methods with promising geometric a priori parameters. Several tests with different values of regularizing parameter were made to bespeak this new regularizing strategy. The inversion results applied to noise-corrupted synthetic gravity data revealed that, regardless of promising starting models, the estimated distribution of point masses and the anomalous mass offered valuable information about the homogeneous sources in the subsurface. Tests on real data from a portion of Quadrilátero Ferrífero, Minas Gerais state, Brazil, were performed for complementary analysis of the proposed inversion method.