本文實例展示了php實現(xiàn)的格魯斯卡爾算法（kruscal）的實現(xiàn)方法，分享給大家供大家參考。相信對于大家的php程序設(shè)計有一定的借鑒價值。

具體代碼如下：

<?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//邊集數(shù)組的邊類class EdgeArc {  private $begin; //起始點  private $end; //結(jié)束點  private $weight; //權(quán)值  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 {  //邊集數(shù)組實現(xiàn)圖  private $vexs; //頂點集合  private $arc; //邊集合  private $arcData; //要構(gòu)建圖的邊信息  private $krus; //kruscal算法時存放森林信息  public function Edge($vexsData, $arcData) {    $this->vexs = $vexsData;    $this->arcData = $arcData;    $this->createArc();  }  //創(chuàng)建邊  private function createArc() {    foreach ($this->arcData as $key => $value) {      $key = str_split($key);      $this->arc[] = new EdgeArc($key[0], $key[1], $value);    }  }  //對邊數(shù)組按權(quán)值排序  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";      }    }  }  //查找子樹的尾結(jié)點  private function findRoot($node) {    while ($this->krus[$node] != "0") {      $node = $this->krus[$node];    }    return $node;  }}?> 

感興趣的讀者可以調(diào)試運行一下本文克魯斯卡爾算法實例，相信會有新的收獲。

php技術(shù)：PHP實現(xiàn)克魯斯卡爾算法實例解析，轉(zhuǎn)載需保留來源！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。