Из того, что я понимаю, ваш график должен состоять из кластеров точек, расположенных близко друг к другу (которые вы рассматриваете как узлы, соединенные друг с другом с помощью коротких / недорогих ребер), но сами кластеры находятся намного дальше друг от друга (возможно, несколькими порядки величины относительно расстояний между точками в кластере).
Вы хотите создать связанный граф так, чтобы используемые ребра были наименее дорогими.
График, который связан таким образом, что общая стоимость ребер в нем минимальна, на самом деле является Минимальным остовным деревом. Существует несколько алгоритмов, которые позволяют вам найти такое дерево из вашего графа. Я бы порекомендовал Алгоритм Крускала для вашего случая использования.
Алгоритм Крускала в основном работает, беря список всех ребер (в вашем случае все n * (n-1) / 2 возможных соединений между узлами), сортируя список в нисходящем порядке и переходя от самого дешевого к большинству дорогие края. Первоначально вы просто берете пустой граф, в котором есть только все ваши узлы и нет ребер - поэтому он состоит из n несвязанных компонентов одного узла. Каждый раз, когда вы обрабатываете ребро, посмотрите, не создает ли ребро цикл на вашем графике. Если он не добавляет его в ваш график, в противном случае пропустите его. Продолжайте, пока весь список не будет обработан. Чтобы проверить, вызывает ли добавление ребра цикл, вы можете использовать структуру данных Disjoint Set (как предположил Лукавск).
Крускала можно также использовать для поиска только кластеров, если это то, что вас интересует. Просто прекратите строить дерево, когда вы доберетесь до края, который слишком дорог, чтобы находиться между соседними узлами. Вы получите график, составленный из отключенных компонентов, каждый из которых представляет кластер, состоящий из узлов, которые расположены близко друг к другу То, как дорого это слишком дорого, это то, что вам придется решить.