DBSCAN算法C实现

下面是DBSCAN算法的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define NOISE -1

typedef struct {
    double x, y;
} Point;

typedef struct {
    int *items;
    int size;
    int capacity;
} List;

void add(List *list, int item) {
    if (list->size == list->capacity) {
        list->capacity *= 2;
        list->items = (int*)realloc(list->items, sizeof(int) * list->capacity);
    }
    list->items[list->size++] = item;
}

void expand_cluster(Point *points, int *labels, int point_id, int cluster_id, double eps, int min_points) {
    List seeds = { .items=NULL, .size=0, .capacity=0 };
    for (int i = 0; i < point_num; ++i) {
        double distance = sqrt(pow(points[point_id].x - points[i].x, 2) + pow(points[point_id].y - points[i].y, 2));
        if (distance < eps) {
            add(&seeds, i);
        }
    }

    if (seeds.size < min_points) {
        labels[point_id] = NOISE;
        return;
    }

    labels[point_id] = cluster_id;
    for (int i = 0; i < seeds.size; ++i) {
        int seed_id = seeds.items[i];
        labels[seed_id] = cluster_id;
        for (int j = 0; j < point_num; ++j) {
            if (labels[j] != -1) {
                continue;
            }

            double distance = sqrt(pow(points[seed_id].x - points[j].x, 2) + pow(points[seed_id].y - points[j].y, 2));
            if (distance < eps) {
                add(&seeds, j);
            }
        }
    }
}

void dbscan(Point *points, int *labels, int point_num, double eps, int min_points) {
    int cluster_id = 0;
    for (int i = 0; i < point_num; ++i) {
        if (labels[i] != -1) {
            continue;
        }

        expand_cluster(points, labels, i, cluster_id, eps, min_points);
        ++cluster_id;
    }
}

int main() {
    Point points[] = {
        {1, 2},
        {2, 3},
        {3, 4},
        {8, 7},
        {8, 8},
        {7, 7},
        {10, 10},
        {20, 20},
        {25, 25}
    };
    int point_num = sizeof(points) / sizeof(Point);

    int *labels = (int*)malloc(sizeof(int) * point_num);
    for (int i = 0; i < point_num; ++i) {
        labels[i] = -1;
    }

    double eps = 3;
    int min_points = 2;

    dbscan(points, labels, point_num, eps, min_points);

    for (int i = 0; i < point_num; ++i) {
        printf("Point (%lf, %lf) is in cluster %d\n", points[i].x, points[i].y, labels[i]);
    }

    free(labels);

    return 0;
}

这里实现的是基础版本的DBSCAN，如果需要更高效的实现，可以使用KD-Tree等数据结构进行优化。