One of the most common algorithm families that can manage non-convex clusters is spectral clustering. The main idea is to project the dataset X on a space where the clusters can be captured by hyperspheres (for example, using K-means). This result can be achieved in different ways, but, as the goal of the algorithm is to remove the concavities of generic shaped regions, the first step is always the representation of X as a graph G={V, E}, where the vertices V ≡ X and the weighted edges represent the proximity of every couple of samples xi, xj ∈ X through the parameter wij ≥ 0. The resulting graph can be either complete (fully connected) or it can have edges only between some sample couples (that is, the weight of non-existing weights is set equal to zero). In the following diagram, there's an example of a partial graph:
