GHS算法：分布式最小生成树算法

题目描述：在一个分布式系统中，多个节点通过通信网络相连，每条边有一个权重。我们需要找到一个最小生成树（MST），即连接所有节点的树结构，使得所有边的权重之和最小。这个问题的挑战在于，每个节点只有局部信息（只知道与自己相连的边），没有全局视图。GHS算法（以发明者Gallager、Humblet和Spira命名）是一个经典的异步分布式MST算法。

解题过程：

1. 问题建模与初始化

   • 系统建模为无向连通图G=(V,E,W)，其中V是节点集合，E是边集合，W是边的权重函数
   • 每个节点初始时是一个独立的"片段"（fragment）
   • 节点只知道：自己的唯一标识符、与邻居相连的边及其权重
   • 目标：通过节点间的消息传递，逐步合并片段，最终形成全局MST

2. 核心思想：片段合并

   • 算法基于片段扩展的思想：从单个节点开始，每个片段寻找连接自己的最小权重边（称为最小出边，MOE）
   • 关键定理：对于任何片段，其MOE必定在全局MST中
   • 算法通过不断合并片段来构建MST，确保每次合并都遵循MST性质

3. 算法步骤详解

   阶段1：片段初始化与MOE寻找

   • 每个节点初始时自成一个片段，片段级别为0
   • 节点向所有邻居发送"连接请求"，包含自己的片段ID和级别
   • 收到请求后，节点记录邻居信息，确定自己的最小出边（权重最小的边）

   阶段2：片段合并协商

   • 当两个片段通过各自的MOE相连时，开始合并协商
   • 较高级别的片段吸收较低级别的片段
   • 如果级别相同，则通过比较片段ID决定哪个片段吸收另一个
   • 吸收过程通过"改变根"消息实现，重新定向片段内的边

   阶段3：片段级别更新

   • 成功合并后，新片段的级别为max(原级别)+1
   • 更新后的片段继续寻找新的MOE，准备下一轮合并
   • 这个过程重复直到所有节点属于同一个片段

4. 消息类型与处理

   • 连接请求：用于发起片段合并
   • 接受/拒绝：回应连接请求
   • 改变根：在片段内重新定向边
   • 报告：向上汇报MOE查找结果
   • 测试：检查边是否连接同一片段

5. 终止条件

   • 当所有节点都属于同一个片段时算法终止
   • 每个节点都知道自己的父节点和子节点，形成树结构
   • 最终得到的树就是全局最小生成树

6. 算法特性

   • 消息复杂度：O(|E| + |V|log|V|)
   • 时间复杂度：O(|V|log|V|)
   • 适用于异步通信模型
   • 具有容错性，能处理消息丢失和节点故障

这个算法的精妙之处在于通过局部信息做出全局最优决策，每个节点只需与邻居通信，就能协同构建出全局MST。