1. 云栖社区>
2. PHP教程>
3. 正文

# PHP实现克鲁斯卡尔算法实例解析

`<?phprequire 'edge.php';\$a = array(  'a',  'b',  'c',  'd',  'e',  'f',  'g',  'h',  'i');\$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');\$test = new Edge(\$a, \$b);print_r(\$test->kruscal());?>`

edge.php文件代码如下：
`<?php//边集数组的边类class EdgeArc {  private \$begin; //起始点  private \$end; //结束点  private \$weight; //权值  public function EdgeArc(\$begin, \$end, \$weight) {    \$this->begin = \$begin;    \$this->end = \$end;    \$this->weight = \$weight;  }  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; //kruscal算法时存放森林信息  public function Edge(\$vexsData, \$arcData) {    \$this->vexs = \$vexsData;    \$this->arcData = \$arcData;    \$this->createArc();  }  //创建边  private function createArc() {    foreach (\$this->arcData as \$key => \$value) {      \$key = str_split(\$key);      \$this->arc[] = new EdgeArc(\$key[0], \$key[1], \$value);    }  }  //对边数组按权值排序  public function sortArc() {    \$this->quicklySort(0, count(\$this->arc) - 1, \$this->arc);    return \$this->arc;  }  //采用快排  private function quicklySort(\$begin, \$end, &\$item) {    if (\$begin < 0(\$begin >= \$end)) return;    \$key = \$this->excuteSort(\$begin, \$end, \$item);    \$this->quicklySort(0, \$key - 1, \$item);    \$this->quicklySort(\$key + 1, \$end, \$item);  }  private function excuteSort(\$begin, \$end, &\$item) {    \$key = \$item[\$begin];    \$left = array();    \$right = array();    for (\$i = (\$begin + 1); \$i <= \$end; \$i++) {      if (\$item[\$i]->getWeight() <= \$key->getWeight()) {\$left[] = \$item[\$i];      } else {\$right[] = \$item[\$i];      }    }    \$return = \$this->unio(\$left, \$right, \$key);    \$k = 0;    for (\$i = \$begin; \$i <= \$end; \$i++) {      \$item[\$i] = \$return[\$k];      \$k++;    }    return \$begin + count(\$left);  }  private function unio(\$left, \$right, \$key) {    return array_merge(\$left, array(      \$key    ) , \$right);  }  //kruscal算法  public function kruscal() {    \$this->krus = array();    \$this->sortArc();    foreach (\$this->vexs as \$value) {      \$this->krus[\$value] = "0";    }    foreach (\$this->arc as \$key => \$value) {      \$begin = \$this->findRoot(\$value->getBegin());      \$end = \$this->findRoot(\$value->getEnd());      if (\$begin != \$end) {\$this->krus[\$begin] = \$end;echo \$value->getBegin() . "-" . \$value->getEnd() . ":" . \$value->getWeight() . "/n";      }    }  }  //查找子树的尾结点  private function findRoot(\$node) {    while (\$this->krus[\$node] != "0") {      \$node = \$this->krus[\$node];    }    return \$node;  }}?>`

40+云计算产品，6个月免费体验