PHP 实现克鲁斯卡尔（Kruskal）最小生成树算法详解

Kruskal 算法核心原理

克鲁斯卡尔算法是寻找加权无向连通图最小生成树的经典方法。其基本思想遵循贪心策略：

1. 初始化森林：将图中的每个顶点视为一个独立的连通分量（初始时包含 $n$ 棵树）。
2. 按权排序：将所有边按照权值从小到大进行排列。
3. 筛选不形成回路的边：从权值最小的边开始扫描。如果所选边连接的两个顶点属于不同的连通分量，则将该边加入最小生成树，并合并这两个连通分量；若属于同一分量，则舍去该边以防形成回路。
4. 终止条件：当加入的边数达到顶点数减一（即所有顶点连通）时，算法结束。

PHP 实现准备

为了在 PHP 中清晰表达图的拓扑关系，我们将采用面向对象的方式定义“边”与“图”的数据结构。主要涉及以下逻辑操作：

• 使用 EdgeArc 类封装单个边的起点、终点与权值信息。
• 使用 Edge 类管理顶点的集合以及由边构成的动态数组。
• 利用递归实现的快排（QuickSort）对边集进行预处理排序。
• 借助 $parent$ 索引数组模拟并查集中的查找根节点操作，以判断连通性。

具体代码实现步骤

第1步：编写主程序入口

首先创建用于测试的数据集，定义顶点集合和边的关联权值，实例化图对象并调用算法。

<?php
require 'edge.php';
// 定义图中的所有顶点
$a = array(
  'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'
);

// 定义边及其对应的权值 (如 ab:10)
$b = array(
  'ab' => '10',
  'af' => '11',
  'gb' => '16',
  'fg' => '17',
  'bc' => '18',
  'bi' => '12',
  'ci' => '8',
  'cd' => '22',
  'di' => '21',
  'dg' => '24',
  'gh' => '19',
  'dh' => '16',
  'de' => '20',
  'eh' => '7',
  'fe' => '26'
);

// 实例化 Edge 对象并执行 Kruskal 算法
$test = new Edge($a, $b);
print_r($test->kruscal());
?>

第2步：构建边与图的基类

实现 EdgeArc 保存每条边的基础属性，Edge 类负责统筹顶点列表和边列表。同时完成将键值对形式的边数据解析为对象的过程。

<?php
// 单条边的数据结构
class EdgeArc {
  private $begin; // 起始点
  private $end;   // 结束点
  private $weight;// 权值

  public function __construct($begin, $end, $weight) {
    $this->begin = $begin;
    $this->end = $end;
    $this->weight = $weight;
  }
  // Getter 方法
  public function getBegin() { return $this->begin; }
  public function getEnd()   { return $this->end; }
  public function getWeight(){ return $this->weight; }
}

class Edge {
  private $vexs;     // 存储所有顶点的数组
  private $arc;      // 存储所有边对象的数组
  private $arcData;  // 原始边数据
  private $krus;     // 用于记录连通关系的临时表

  public function __construct($vexsData, $arcData) {
    $this->vexs = $vexsData;
    $this->arcData = $arcData;
    $this->createArc();
  }

  // 将传入的数组转换为边对象存入 $this->arc
  private function createArc() {
    foreach ($this->arcData as $key => $value) {
      $keys = str_split($key); // 'ab' => ['a','b']
      $this->arc[] = new EdgeArc($keys[0], $keys[1], $value);
    }
  }
}
?>

第3步：实现边权值的快速排序

为了让算法优先处理小权值的边，必须对 $this->arc 数组中的元素依据 getWeight() 的结果进行升序排列。此处复用了一套简易的快速排序逻辑。

  // 对外暴露的排序方法
  public function sortArc() {
    $this->quicklySort(0, count($this->arc) - 1, $this->arc);
    return $this->arc;
  }

  // 快速排序驱动
  private function quicklySort($begin, $end, &$item) {
    if ($begin >= $end) return;
    $keyPos = $this->excuteSort($begin, $end, $item);
    $this->quicklySort($begin, $keyPos - 1, $item);      //修正了原文错误的左区间参数
    $this->quicklySort($keyPos + 1, $end, $item);
  }

  // 分区操作
  private function excuteSort($begin, $end, &$item) {
    $pivot = $item[$begin];
    $left = array();
    $right = array();
    
    for ($i = ($begin + 1); $i <= $end; $i++) {
      if ($item[$i]->getWeight() <= $pivot->getWeight()) {
        $left[] = $item[$i];
      } else {
        $right[] = $item[$i];
      }
    }
    
    // 将结果拼接并覆盖原数组部分
    $result = array_merge($left, array($pivot), $right);
    for ($i = $begin; $i <= $end; $i++) {
      $item[$i] = $result[$i - $begin];
    }
    
    // 返回基准元素最终所在的下标
    return $begin + count($left);
  }

第4步：Kruskal 核心循环与并查集判定

这是最核心的逻辑部分。$this->krus 数组充当了父节点指针表。初始状态下每个顶点的值为 "0"（表示它自己就是自己的根）。如果在一次遍历中发现某条边的两个顶点有相同的根节点，说明它们已经连通，跳过该边即可防止成环。

  // 克鲁斯卡尔主逻辑
  public function kruscal() {
    $this->krus = array();
    $this->sortArc(); // 先保证边是按权值从小到大的顺序
    
    // 初始化每个顶点所属的子树根为自己
    foreach ($this->vexs as $value) {
      $this->krus[$value] = "0"; 
    }
    
    foreach ($this->arc as $key => $value) {
      $startRoot = $this->findRoot($value->getBegin());
      $endRoot   = $this->findRoot($value->getEnd());
      
      // 如果根节点不同，则合并两棵子树，该边入选最小生成树
      if ($startRoot != $endRoot) {
        $this->krus[$startRoot] = $endRoot; // 建立父子映射，合并成一个连通域
        echo $value->getBegin() . "-" . $value->getEnd() . ":" . $value->getWeight() . "\n";
      }
    }
  }
  
  // 向上追溯直到找到根节点（也就是值为 0 的那一级）
  private function findRoot($node) {
    while ($this->krus[$node] != "0") {
      $node = $this->krus[$node];
    }
    return $node;
  }

运行结果与总结

以上即为 PHP 实现克鲁斯卡尔算法解决最小生成树问题的详细内容。该实现方案结构简单，适合初学者理解图论中避免构成回路的判定过程。更多关于 PHP 高级算法应用的资料请关注本站其它相关文章！