BFS聚类算法C++实现：从原理到高性能代码实战

1次阅读

没有评论

共计 3329 个字符，预计需要花费 9 分钟才能阅读完成。

在处理图数据聚类问题时，传统的 K -means 等算法存在明显的局限性。它们通常需要预先指定聚类数量，且对非凸形状的聚类效果不佳。相比之下，BFS（广度优先搜索）算法在社区发现和图聚类任务中展现出独特优势：

无需预先指定聚类数量
能够自然地发现数据中的连通分量
对不规则形状的聚类效果良好
特别适合社交网络、推荐系统等场景

在聚类任务中，DFS（深度优先搜索）和 BFS 各有特点：

时间复杂度：
DFS: O(V + E)
BFS: O(V + E)
理论上相同，但实际表现差异明显
内存占用：
DFS: 递归实现需要 O(V)的栈空间
BFS: 需要 O(V)的队列空间
对于深度大的图，DFS 可能引发栈溢出
聚类特性：
BFS 更易发现 ” 半径 ” 较小的紧密社区
DFS 可能跨越多个社区，导致聚类结果分散

使用 vector<unordered_set> 存储邻接表，既节省空间又能快速查询：

class Graph {
    std::vector<std::unordered_set<size_t>> adj_list;

public:
    explicit Graph(size_t vertex_count) : adj_list(vertex_count) {}

    void add_edge(size_t u, size_t v) {adj_list[u].insert(v);
        adj_list[v].insert(u); // 无向图
    }

    const auto& neighbors(size_t u) const {return adj_list[u]; }
};

利用 C ++17 的并行算法加速处理：

#include <execution>
#include <algorithm>

void parallel_bfs(const Graph& g, size_t start) {std::vector<bool> visited(g.vertex_count(), false);
    std::queue<size_t> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {auto current = q.front();
        q.pop();

        // 并行处理邻居节点
        std::for_each(std::execution::par,
                      g.neighbors(current).begin(),
                      g.neighbors(current).end(),
                      [&](auto neighbor) {if (!visited[neighbor]) {visited[neighbor] = true;
                              q.push(neighbor);
                          }
                      });
    }
}

避免 vector<bool> 的特殊处理带来的性能问题：

class VisitedTracker {
    std::vector<uint8_t> visited; // 每个 bit 表示一个节点的访问状态

public:
    explicit VisitedTracker(size_t size) : visited((size + 7) / 8) {}

    bool is_visited(size_t node) const {return visited[node/8] & (1 << (node%8));
    }

    void mark_visited(size_t node) {visited[node/8] |= (1 << (node%8));
    }
};

以下是一个完整的高性能 BFS 聚类实现：

/**
 * @file bfs_clustering.h
 * @brief BFS-based graph clustering implementation
 */

#include <vector>
#include <unordered_set>
#include <queue>
#include <atomic>
#include <mutex>
#include <execution>

class ThreadSafeQueue {
    std::queue<size_t> q;
    std::mutex mtx;

public:
    void push(size_t node) {std::lock_guard<std::mutex> lock(mtx);
        q.push(node);
    }

    bool try_pop(size_t& node) {std::lock_guard<std::mutex> lock(mtx);
        if (q.empty()) return false;
        node = q.front();
        q.pop();
        return true;
    }

    bool empty() const {std::lock_guard<std::mutex> lock(mtx);
        return q.empty();}
};

class BFSClustering {
    const Graph& graph;
    std::vector<std::atomic<bool>> visited;

public:
    explicit BFSClustering(const Graph& g) : graph(g), visited(g.vertex_count()) {}

    std::vector<std::vector<size_t>> compute_clusters() {
        std::vector<std::vector<size_t>> clusters;

        for (size_t i = 0; i < graph.vertex_count(); ++i) {if (!visited[i].load(std::memory_order_acquire)) {clusters.emplace_back(bfs_from(i));
            }
        }

        return clusters;
    }

private:
    std::vector<size_t> bfs_from(size_t start) {
        std::vector<size_t> cluster;
        ThreadSafeQueue q;

        q.push(start);
        visited[start].store(true, std::memory_order_release);

        while (!q.empty()) {
            size_t current;
            if (q.try_pop(current)) {cluster.push_back(current);

                std::for_each(std::execution::par,
                             graph.neighbors(current).begin(),
                             graph.neighbors(current).end(),
                             [&](size_t neighbor) {
                                 bool expected = false;
                                 if (visited[neighbor].compare_exchange_strong(expected, true, std::memory_order_acq_rel)) {q.push(neighbor);
                                 }
                             });
            }
        }

        return cluster;
    }
};

我们在 100 万节点的社交网络图上测试：