预备知识

条件变量

std::mutex 用于在多个线程访问同一共享变量时提供互斥保护。一个线程持有锁时，其他尝试获取该锁的线程会阻塞，直到锁被释放。互斥量可以隔离访问，但不能单独表达线程之间的执行依赖。

条件变量用于协调多个线程的执行顺序。例如，消费者线程需要等待生产者准备好数据后再处理。条件变量提供等待和通知两类操作，是线程同步的常用机制。

std::condition_variable 提供了实现线程间状态通知的基础。为了避免竞态条件，它必须与互斥量（通常结合 std::unique_lock）配合使用。wait 操作的底层执行逻辑包含三个关键动作：

  1. 释放并睡眠：当线程调用 wait 时，它会原子性地释放当前持有的互斥锁，并将当前线程置于阻塞队列中等待。这确保了其他工作线程能够获取互斥锁进而修改共享数据。
  2. 唤醒与重加锁：当条件变量接收到唤醒通知后，线程结束睡眠。但在 wait 函数真正返回之前，该线程会自动尝试重新获取与之关联的互斥锁。
  3. 防范虚假唤醒：操作系统在极少数情况下可能会在没有收到明确唤醒信号时将等待线程唤醒，这被称为“虚假唤醒”。因此，wait 调用必须嵌套在条件判断的循环（如 while 循环）中，线程被唤醒后需立刻复核共享变量的状态是否符合预期，若不符合则继续进入等待状态。

当共享资源完成更新时，执行更新的线程需要通过条件变量发送通知：

  • notify_one：该接口仅唤醒阻塞队列中的一个线程。具体唤醒哪一个通常由底层的操作系统调度器决定。这种方式适用于资源的增加仅能满足单一线程处理需求的场景（如任务队列中新增了一个任务），能够有效节约系统开销。
  • notify_all：该接口会唤醒所有阻塞在该条件变量上的线程。它适用于全局状态发生改变，且该改变对所有子线程都有意义的场景（例如主控线程完成基础配置后，通知所有工作线程同步启动计算）。

实际应用中应谨慎使用 notify_all。所有被唤醒线程都会重新竞争同一把互斥锁，除一个线程成功获锁外，其余线程可能再次阻塞。这种集中唤醒引发的锁竞争和上下文切换称为“惊群效应”。

POSIX 线程库提供了底层原语来构建消息队列同步机制。以下代码展示了如何在 C 语言环境下利用 POSIX 线程库实现基于条件变量的消息队列管理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/* POSIX 线程库，提供互斥锁和条件变量。 */
#include <pthread.h>
/* 消息节点。 */
struct msg {
    /* 指向下一条消息，用于构成单向链表队列。 */
    struct msg *m_next;
    /* more stuff here */
};

/* 工作队列头指针，由生产者和消费者共享。 */
struct msg *workq;
/* 条件变量：队列从空变为非空时通知消费者。 */
pthread_cond_t qready = PTHREAD_COND_INITIALIZER;
/* 互斥锁：保护 workq 的读写。 */
pthread_mutex_t qlock = PTHREAD_MUTEX_INITIALIZER;

/* 消费者循环处理消息。 */
void process_msg(void) {
    /* mp 保存本轮取出的消息。 */
    struct msg *mp;
    /* 消费者通常长期运行，持续等待并处理队列任务。 */
    for (;;) {
        /* 加锁后才能检查共享队列。 */
        pthread_mutex_lock(&qlock);
        /* 使用 while 防止虚假唤醒，或醒来后队列已被其他消费者取空。 */
        while (workq == NULL)
            /* wait 会原子释放 qlock 并睡眠；返回时重新持有 qlock。 */
            pthread_cond_wait(&qready, &qlock);
        /* 取出队首消息。 */
        mp = workq;
        /* 更新共享队列头。 */
        workq = mp->m_next;
        /* 共享队列修改完成，释放锁。 */
        pthread_mutex_unlock(&qlock);
        /* now process the message mp */
    }
}

/* 生产者把消息插入工作队列。 */
void enqueue_msg(struct msg *mp) {
    /* 生产者也必须在同一把锁下修改 workq。 */
    pthread_mutex_lock(&qlock);
    /* 新消息头插到当前队列前端。 */
    mp->m_next = workq;
    /* 发布新的队列头。 */
    workq = mp;
    /* 释放锁后再通知可减少被唤醒线程立即抢锁失败的概率。 */
    pthread_mutex_unlock(&qlock);
    /* 通知至少一个等待的消费者队列状态可能已改变。 */
    pthread_cond_signal(&qready);
}

在上述实现中，消费者线程获取互斥锁后必须循环检查工作队列是否为空。原因包括虚假唤醒，以及线程被唤醒后重新获取锁前，消息已被其他消费者取走。循环检查配合条件变量等待，可以避免无效轮询。

条件变量的标准读法是“锁保护状态，条件变量负责睡眠和唤醒”。wait 本身不代表条件一定满足，它只是让线程在条件可能改变时醒来。因此工程代码通常写成 wait(lock, predicate) 或 while (!predicate) wait(...)，把真正的业务条件放在谓词中反复检查。

并查集

并查集用于管理一组互不相交的等价类，适合快速判断元素归属和合并集合。在最小生成树构造中，判断一条新边是否会成环，本质上就是判断该边两个端点是否属于同一连通分量。

并查集的核心操作是查找和合并。查找返回元素所属等价类的代表元素；合并将两个不同等价类合并。初始状态下，每个元素各自构成一个单元素集合。

最直接的实现称为快速查找/慢速合并。系统维护一个数组，索引代表元素，数组值代表所属集合标识。查找可通过索引直接完成，时间复杂度为常数；但合并需要遍历整个数组，将一个集合的所有标识更新为另一个集合标识，因此合并为线性时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 快速查找版本并查集：find 为 O(1)，union 为 O(n)。
class UnionFind:
    # n 是元素数量，元素编号默认为 0 到 n - 1。
    def __init__(self, n):
        # 保存元素总数，union 时需要全表扫描。
        self.n = n
        # group[k] 表示元素 k 当前所属集合编号。
        self.group = [k for k in range(n)]

    # 返回元素 k 所属集合编号。
    def find(self, k):
        return self.group[k]

    # 合并元素 i 和 j 所在集合。
    def union(self, i, j):
        # 读取两个元素当前所属集合编号。
        iGroup, jGroup = self.group[i], self.group[j]
        # 已在同一集合时无需修改。
        if iGroup == jGroup: return
        # 扫描所有元素，把 jGroup 改写为 iGroup。
        for k in range(self.n):
            if (self.group[k] == jGroup): self.group[k] = iGroup

为提升合并效率，可以将结构从扁平数组改为森林模型。系统不再记录集合标识，而是维护父节点索引数组。初始时，每个元素是一棵单节点树，父节点指向自身。集合代表元素变为树根。

基于树形结构的策略称为快速合并。合并两个集合时，算法先沿父节点数组找到两棵树的根，再将其中一个根的父指针改为另一个根。这样用少量指针修改替代全数组遍历。

单纯快速合并可能在特定合并顺序下退化为链表，使查找路径过长。加权优化额外维护树规模或秩。合并时，将规模较小的树挂到规模较大的树根上，从而限制树高增长。

路径压缩优化查找操作。查找某个元素根节点时，算法沿父指针向上遍历，并将路径上的中间节点直接连接到最终根节点。一次查找后，该路径被扁平化，后续查找成本降低。若配合按秩或按规模合并，并查集操作的均摊复杂度可达到近似常数的 O(α(n))O(\alpha(n))，其中 α(n)\alpha(n) 是增长极慢的反 Ackermann 函数。

并查集的不同版本可以按“哪个操作快”来记忆。快速查找用数组直接存集合编号，find 很快但 union 要全表改编号；快速合并用父指针森林表示集合，union 只改根指针但 find 可能走长链；按秩合并和路径压缩则分别控制树高、扁平化访问路径，是工业实现中最常搭配使用的两项优化。

串行最小生成树

并行化设计前，先回顾串行最小生成树算法。最经典的贪心策略是 Prim 算法和 Kruskal 算法，二者都通过局部最优选择逐步构造全局最优解。

Prim 算法

Prim 算法基于顶点扩张。算法可从任意起点开始，逐步将相邻顶点纳入生成树。执行过程中维护两个顶点集合：已纳入生成树的顶点和尚未纳入的顶点。每一步在跨越两个集合的边中选择最小权重边，将其连接的未纳入顶点加入生成树，并把该边加入结果集，直到所有顶点被纳入。

以下是基于邻接矩阵实现的 Prim 算法逻辑。利用邻接矩阵存储图时，二维数组中的元素直接记录了顶点间的边权重。若两个顶点间不存在直接连接，则将其权重初始化为无穷大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 任选一个起始顶点。
int start = 1;
// 初始化每个顶点到当前生成树的最小接入边。
for (int i = 1; i <= vertex_num; i++)
{
    // dis[i][0] 保存当前生成树到顶点 i 的最短边权。
    dis[i][0] = edge_map[start][i];
    // dis[i][1] 保存提供该最短边的树内顶点。
    dis[i][1] = start;
    // mark[i] 为 0 表示顶点 i 尚未加入生成树。
    mark[i] = 0;
}
// 起点先加入生成树。
mark[start] = 1;
// 已加入生成树的顶点数量。
vertex_count++;

// 每轮向生成树加入一个新顶点，直到覆盖全部顶点。
while (vertex_count < vertex_num)
{
    // min 保存当前跨割最小边权。
    int min = INF;
    // k 保存本轮将加入生成树的顶点。
    int k = 0;
    // 在线性扫描中寻找未加入顶点的最小接入边。
    for (int i = 1; i <= vertex_num; i++)
        if (mark[i] == 0 && min > dis[i][0])
        {
            min = dis[i][0];
            k = i;
        }
    // k 仍为 0 表示剩余顶点不可达，图不连通。
    if (k == 0)
        break;
    // 将顶点 k 加入生成树。
    mark[k] = 1;
    // 记录连接 k 的生成树边起点。
    path[vertex_count][0] = dis[k][1];
    // 记录连接 k 的生成树边终点。
    path[vertex_count][1] = k;
    // 已加入顶点数增加。
    vertex_count++;
    // 用新加入顶点 k 刷新其余未加入顶点的最短接入边。
    for (int i = 1; i <= vertex_num; i++)
        if (mark[i] == 0 && dis[i][0] > edge_map[k][i])
        {
            // k 到 i 的边更便宜，更新最小接入边权。
            dis[i][0] = edge_map[k][i];
            // 记录提供该边的新树内顶点。
            dis[i][1] = k;
        }
}

上述实现中，距离数组维护未纳入顶点到已纳入顶点集合的最短单边距离。第一列存权重，第二列存提供该权重的树内顶点索引。标志数组记录顶点是否已纳入生成树。主循环扫描距离数组找到全局最小值对应顶点；新顶点加入后，再遍历未纳入顶点并更新其最短接入边。由于每轮都要线性扫描，时间复杂度为顶点数平方，适合稠密图，在大规模稀疏图上效率较低。

Prim 算法维护的是一个不断长大的连通块。dis[i][0] 不是源点到 i 的路径距离，而是“从当前生成树边界接到 i 的最便宜单条边”。这一点容易和 Dijkstra 混淆：Prim 优化的是整棵树的总接入成本，不关心从起点到某个顶点的路径是否最短。

Kruskal 算法

Kruskal 算法从边的视角构造最小生成树。初始状态是一片森林，每个顶点自成一棵树。算法不断选择合法边合并不同树，直到形成唯一生成树。

算法首先将图中所有的边按权重以非降序排列，然后构建一个仅包含顶点不包含任何边的森林。接下来重复从排序表中取出权值最小的边，如果这条边加入森林后不会在其中形成环路，那么将此边加入结果集，否则直接丢弃这条边。向结果集中加完顶点数减一条边后算法结束，此时的结果集即为图的最小生成树。

在代码实现层面，边结构的定义通常通过重载小于运算符来实现基于权重的排序。为解决环路判定与集合合并的性能瓶颈，标准实现均依赖于前文所述的并查集数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// Kruskal 使用的边记录。
class Edge
{
public:
    // 边的一个端点。
    int u;
    // 边的另一个端点。
    int v;
    // 边权。
    int w;
    // 小于运算符用于按边权排序。
    friend bool operator<(const Edge & E1, const Edge& E2)
    {
        // 权重较小的边排在前面。
        return E1.w < E2.w;
    }
};

// 串行 Kruskal 算法；edges 假定已按权重排序。
void Kruskal (const vector<Edge>& edges, int n)
{
    // uset 是并查集父数组或集合标识数组。
    vector<int> uset;
    // SpanTree 保存最终选入 MST 的边。
    vector<Edge> SpanTree;
    // Cost 累计 MST 总权重；e1/e2 保存两个端点所属集合。
    int Cost = 0, e1, e2;
    // 初始化并查集，每个顶点单独成分量。
    MakeSet(uset, n);
    // 假设edges已经按照权重从小到大排序。
    for (size_t i = 0; i < edges.size() && SpanTree.size() < (size_t)(n - 1); i++)
    {
        // 查找端点 u 所属连通分量。
        e1 = FindSet(uset, edges[i].u);
        // 查找端点 v 所属连通分量。
        e2 = FindSet(uset, edges[i].v);
        // 两端点不在同一分量时，加入该边不会形成环。
        if (e1 != e2)
        {
            // 将该边加入 MST。
            SpanTree.push_back(edges[i]);
            // 累加 MST 权重。
            Cost += edges[i].w;
            // 合并两个连通分量。
            uset[e1] = e2;
        }
    }
}

Kruskal 首先对全体边排序，因此排序主导整体复杂度。若使用高效并查集管理连通分量，合并与查询均摊成本很低，整体复杂度主要由排序决定。该特性使 Kruskal 适合边数较少的稀疏图。

Kruskal 的视角和 Prim 相反。Prim 始终保持“一棵树”向外扩张；Kruskal 一开始有很多棵小树，每加入一条合法边就合并两个连通分量。并查集在这里承担的就是“这条边的两个端点是否已经在同一棵树里”的快速环路判定。

在现实生活中，社交关系网通常具有动态特征，例如两人建立或解除好友关系对应着边的增减，通信成本变化对应着边权重的改变。维护动态图的最小生成树结果一般需要使用如 B 树等高级索引结构对图中的边和点信息建立索引。现有的理论表明，基于索引的动态维护算法可以在立方根对数级别的时间内完成维护工作。

并行最小生成树

图的划分

网络规模增长后，串行 MST 算法可能成为瓶颈。并行算法通常先划分图，将原图拆成若干不相交分区，交由不同进程或线程处理。各分区完成局部计算后，将结果交给全局进程继续合并，得到完整最小生成树。

为支持并行处理，图通常从邻接矩阵改为更节省内存的邻接表。数据结构中还需要记录多线程状态标识。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 并行图结构中的边节点。
class edge
{
public:
    // 默认构造空边，tid=-1 表示尚未分配给线程。
    edge() : v1(0), v2(0), w(0), tid(-1), next(NULL) {}
    // 构造指定端点和权重的边。
    edge(int a, int b, int c) : v1(a), v2(b), w(c), tid(-1), next(NULL) {}
    // 边的两个端点。
    int v1, v2;
    // w 是边权；tid 记录该边当前由哪个线程分区处理。
    int w, tid;
    // 邻接表中的下一条边。
    edge* next;
};

// 并行图结构中的顶点节点。
class vertex
{
public:
    // vid 是顶点编号，next 指向该顶点的第一条邻接边。
    vertex(int v = 0) : vid(v), next(NULL) {}
    // 顶点编号。
    int vid;
    // 指向第一条邻接边。
    edge* next;
};

在这里，边的类定义中包含了一个记录处理该边的线程编号的变量，该变量在后续的并发归约过程中用于追踪数据来源。图的构建函数负责读取输入数据并建立顶点数组与链表结构的映射关系。

分配任务前需要确定图划分规则。划分要求每个顶点只属于一个子图，保证无遗漏且无重叠。MST 并行算法通常希望各分区负载均衡，因此可用哈希或取模方式划分顶点，例如对顶点索引按线程数取模，将顶点分散到不同线程分区。

1
2
3
4
5
6
7
8
9
10
11
12
// 按顶点编号把图划分给不同工作线程。
void partition()
{
    // temp[i] 保存分配给第 i 个线程的顶点子集。
    vector<vector<vertex>> temp(thread_num);
    // 取模划分顶点，保证每个顶点只进入一个分区。
    for (int i = 0; i < (int)graph.size(); i++)
        temp[i % thread_num].push_back(graph[i]);
    // 为每个分区启动一个工作线程。
    for (int i = 0; i < thread_num; i++)
        subthreads.push_back(thread(subthread_func, temp[i], i));
}

基于边并行

基于边的并行最小生成树算法也可称作并行 Kruskal 算法，其主体思想与非并行化的 Kruskal 算法大致相同。整个算法解耦为由各并行进程完成的部分算法与由一个全局进程完成的仲裁算法。

在部分算法中，各并行子线程独立扫描分配给自身的子图分区。为快速提取具有最小权重的边，子线程内部借助基于红黑树实现的有序多重映射容器来组织辖区内的边数据。遍历所有分配到的顶点及其邻接链表，将边权重作为键值插入映射容器中，从而完成局部的非降序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 工作线程函数：维护本分区的局部有序边流。
void subthread_func(vector<vertex> v, int tid)
{
    // multimap 按边权自动排序，并允许相同权重的多条边。
    multimap<int, edge> e;
    // 扫描分配给本线程的所有顶点。
    for (int i = 0; i < (int)v.size(); i++)
    {
        // temp 遍历当前顶点的邻接边链表。
        edge* temp = v[i].next;
        while (temp!= NULL)
        {
            // 标记该边来自当前分区线程。
            temp->tid = tid;
            // 以边权作为 key 放入有序容器。
            e.insert(pair<int, edge>(temp->w, *temp));
            // 继续扫描邻接链表。
            temp = temp->next;
        }
    }
    // 进入共享状态更新区。
    unique_lock<mutex> lk(mut);
    // 发送本分区当前最小边；若没有边可发送，标记分区完成。
    if (!send_edge(e))
        partition_finished[tid] = true;
    // 记录该线程已完成初始局部排序。
    ready_threads++;
    // 通知仲裁线程：有线程准备就绪。
    ready_cond.notify_one();
    // 通知仲裁线程：全局边队列可能已有新边。
    arbiter_cond.notify_one();
    // 等待仲裁线程请求本分区继续补边。
    while (true)
    {
        // 教学简化；工程代码应使用谓词抵御虚假唤醒。
        cond_v[tid].wait(lk);
        // 全局算法完成时退出线程函数。
        if (isfinished)
            return;
        // 再发送本分区当前最小边；若耗尽则标记完成。
        if (!send_edge(e))
            partition_finished[tid] = true;
        // 通知仲裁线程有新边或分区完成状态可读。
        arbiter_cond.notify_one();
    }
}

当局部边集排序完成后，子线程与全局仲裁进程建立交互。子线程提取当前权重最小的一条边，并在互斥锁的保护下将其写入全局共享的消息队列中。若当前分区内的所有边已处理完毕，线程将更新全局状态数组宣告自身任务终结。随后，线程唤醒等待条件变量的仲裁进程，并使自身进入休眠状态，等待仲裁进程在处理完当前边后发送补充新边的请求指令。

这套并行 Kruskal 不是让每个线程独立产出一棵 MST，而是让每个线程维护一个“局部有序边流”。仲裁线程每次只从各个边流的当前最小边里挑全局最小值，类似多路归并排序中的最小头元素选择。这样可以避免一次性把所有边都集中到全局队列中。

仲裁算法

全局进程所执行的仲裁算法扮演着收集、判定与拼装的职责。全局进程首先向所有并行进程发送消息获取各分区最小权重边构成队列。接下来循环取出队列中权值最小的边，并向提供该边的进程发送消息请求补充新的最小权重边至队列中。这种消耗一条并补充一条的按需拉取机制有效控制了全局共享队列的内存占用，同时保障了全局进程总是能够在来自各个分区的局部最优边中筛选出全局最优解。

如果取出的候选边加入到结果集中不会构成环路则保留此边，若会构成环路则将其丢弃。当结果集中的边的数量达到顶点总数减一或全局队列为空时算法结束，同时通知各进程结束算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 仲裁线程执行的并行 Kruskal 主循环。
void kruskal()
{
    // index[v] 记录顶点 v 当前所属连通分量编号，-1 表示尚未归属。
    map<int, int> index;
    // rev_index[c] 记录连通分量 c 中包含的顶点列表。
    map<int, vector<int>> rev_index;
    // 初始化所有顶点为未归属状态。
    for (int i = 0; i < (int)graph.size(); i++)
        index[i + 1] = -1;
    {
        // 等待所有工作线程完成局部排序并发送第一条候选边。
        unique_lock<mutex> lk(mut);
        ready_cond.wait(lk, [&] { return ready_threads == thread_num; });
    }
    // MST 需要 graph.size() - 1 条边。
    while (mst.size() < graph.size() - 1)
    {
        // 访问全局候选边队列前持锁。
        unique_lock<mutex> lk(mut);
        // 等待队列非空，或所有分区都已耗尽。
        arbiter_cond.wait(lk, [&] {
            return !edge_queue.empty() || all_partitions_finished();
        });
        // 队列为空且无分区可继续供边，算法结束。
        if (edge_queue.empty())
            break;
        // 取出当前全局最小候选边。
        pair<int, edge> temp = *(edge_queue.begin());
        // 从全局候选队列移除该边。
        edge_queue.erase(edge_queue.begin());
        // 释放锁后再通知，减少被唤醒线程的锁竞争。
        lk.unlock();
        // 请求提供该边的分区补充下一条局部最小边。
        cond_v[temp.second.tid].notify_all();
        // 重新加锁，等待该分区补边或宣告完成。
        lk.lock();
        arbiter_cond.wait(lk, [&temp] {
            return partition_finished[temp.second.tid] ||
                   has_edge_from_thread(temp.second.tid);
        });
        // 边队列同步完成，释放共享锁后执行连通性判断。
        lk.unlock();
        // 若两个端点不在同一分量，或二者都未归属，则候选边不会成环。
        if (index[temp.second.v1]!= index[temp.second.v2] ||
            index[temp.second.v1] == -1)
            // 将边加入 MST，并更新连通分量映射。
            add_edge(temp.second, index, rev_index);
    }
    {
        // 设置全局结束标记，通知工作线程退出等待循环。
        unique_lock<mutex> lk(mut);
        isfinished = true;
    }
    // 唤醒并回收所有工作线程。
    for (int i = 0; i < thread_num; i++)
    {
        cond_v[i].notify_all();
        subthreads[i].join();
    }
}

在该并行实现中，边数据按需异步提取，仲裁进程用双向映射字典替代标准数组并查集进行环路判定。一个字典记录顶点到连通分量标识的映射，另一个记录每个连通分量包含的顶点列表。加入候选边时，若两个端点都无归属，则创建新连通分量；若只有一个端点有归属，则将另一个端点并入；若两个端点属于不同分量，则将较小分量并入较大分量，并同步更新顶点映射。该逻辑用于追踪局部生成树合并过程。

仲裁线程的职责可以拆成三步：取当前全局最轻候选边、判断它是否连接两个不同连通分量、通知提供该边的分区补充下一条边。条件变量在这里不是为了保护数据本身，而是为了协调“子线程供边”和“仲裁线程消费边”的节奏。

性能评估

并行改造的有效性可以通过控制变量法下的执行时间来量化验证。在相同硬件环境下，以不同的图拓扑规模及线程数量为参数对串行与并行方案进行了基准测试。

以下表格展示了固定图规模并更改线程数量时的性能演变情况。数值代表毫秒级别的处理耗时。

顶点数，边数 串行算法 双线程 三线程 四线程
2000，10000 239.020 131.375 103.655 81.243
2000，50000 134.275 311.214 178.475 105.061
2000，100000 175.896 426.832 215.936 142.368
5000，10000 319.596 516.655 343.403 313.784
5000，50000 261.326 640.914 379.314 234.928
5000，100000 278.058 750.968 421.656 236.461
10000，10000 477.118 1108.250 651.409 378.871
10000，50000 544.600 1143.080 706.321 397.773
10000，100000 537.772 1451.580 677.460 386.310

测试中，双线程配置受上下文切换、互斥锁竞争和条件变量调度开销影响，在部分用例中慢于串行。线程数增加到四线程后，多核处理收益超过同步开销，四线程配置在各数据规模下均优于串行。

针对更大规模的数据集，测试分别记录了顶点数在八千至三万两千区间，边数在八万至八百万区间的耗时情况。单位为秒。

顶点数 \ 边数 80000 (串行) 800000 (串行) 8000000 (串行)
8000 0.110000 1.490000 19.150000
16000 0.090000 1.670000 20.060000
32000 0.110000 1.520000 20.740000

以下表格展示了相同网络规模下，配置为十六个并发线程的并行算法耗时表现。单位为秒。

顶点数 \ 边数 80000 (并行) 800000 (并行) 8000000 (并行)
8000 0.120000 0.400000 2.190000
16000 0.210000 0.560000 2.870000
32000 0.430000 0.770000 3.420000

对比上述数据可以看出，随着图边密度上升，串行算法中对千万级数组的全局排序操作成为制约性能的主要瓶颈，其执行时间呈现超线性增长。当处理三万两千个顶点、八百万条边的密集图时，并行方案利用多线程分散规约和有序拉取的优势，耗时不到三点五秒，相对于串行方案约二十秒的耗时取得了接近六倍的加速比。

测试中还涉及了部分极高负载组合，例如一万个顶点与四万条边并行耗时超过一万五千毫秒，而四万个顶点与八万条边的组合耗时接近四万五千毫秒。这些边缘用例的数据反映出对于特定分布的拓扑结构，哈希划分策略可能导致部分线程分配到大量高权值的冗余边，进而在全局队列同步时引发剧烈的锁冲突。

基于顶点并行

基于边的并行 Kruskal 虽然可多线程完成局部排序，但仍依赖中心化全局队列进行仲裁。该模型在中等规模下有效，但在更大规模下会受到全局队列锁竞争限制。因此，可以采用基于顶点的并行算法：各并行进程执行分区 Prim，全局进程再执行 Boruvka 合并。

非并行的 Boruvka 算法在起始阶段构造一个仅包含全图所有顶点但不包含任何边的空结果集，此时每一个顶点都属于一个独立的连通分量。算法在每一次迭代中对于每个连通分量，找出具有最小权重的邻接边，即连接该分量内部顶点与外部顶点的权重最小的边。将所有连通分量找出的最小邻接权重边统一并入结果集中。重复此探测并合并的过程直到图中只存在一个连通分量为止。由于在同一轮迭代内，对不同连通分量的邻接边查找操作相互独立，Boruvka 算法具有天然的并行亲和性。

分区 Prim 算法中，系统为当前进程分配特定的顶点子集及其相关的边集。初始状态下，认为分区内的所有顶点均不属于任何连通分量，并构建空的局部结果集。

执行过程中，进程在分区内随机选取一个不属于任何连通分量的游离顶点，为其创建专属的连通分量，并以该组件为起点在全图上执行一步 Prim 算法逻辑。具体而言，算法寻找连接该组件内部顶点与外部顶点的具有最小权重的边。

当找到满足条件的最小连接边后，依据该边指向的外部目标顶点的位置和状态决定后续操作。如果目标顶点存在于本分区的管理范围内且尚处于游离状态，则将此边并入局部结果集中，同时将目标顶点吸纳进当前连通分量，并继续在该扩大的连通分量上循环执行下一步的连接边探测。如果目标顶点在本分区内但已经被划入其他已存在的连通分量，则同样保留此边，将当前的连通分量与目标顶点所在的连通分量合并，并立刻终止当前连通分量的 Prim 探测逻辑。最关键的防冲突机制在于，如果最小连接边指向的外部顶点不在本分区的管辖范围内，为避免产生跨线程的分布式锁与通讯开销，进程将直接放弃向外扩张，停止针对该组件的探测。随后，进程再次在分区内寻找其他游离顶点作为新的探测起点，直到分区内所有顶点都被分配到某个连通分量内。此时生成的局部结果集即为该进程阶段性输出的边集。

各分区先在局部范围内消除大量顶点和边，将原图压缩为由少量跨区连通分量组成的粗粒度网络。局部计算结束后，全局进程收集并合并局部结果，构建包含原始顶点和已确认边的新图。随后在该图上执行串行 Boruvka 算法，通过全局收缩与组件合并，最终得到完整最小生成树边集。

基于顶点的并行方案把工作分成“局部先缩小问题”和“全局再合并组件”两段。局部 Prim 尽量在分区内部先确定容易处理的边，减少全局阶段需要处理的碎片；Boruvka 则适合全局阶段，因为每个连通分量寻找自己的最轻外连边这一动作天然可以并行。