Analysis of an example of Kruskal algorithm implemented by PHP
- 2021-07-16 01:55:53
- OfStack
This article example shows the implementation of PHP Gruskal algorithm (kruscal), sharing for your reference. I believe it has a certain reference value for everyone's PHP programming.
The specific code is as follows:
<?php
require '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());
?>
The code for the edge. php file is as follows:
<?php
// Edge class of edge set array
class EdgeArc {
private $begin; // Starting point
private $end; // End point
private $weight; // Weight value
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 {
// Implementation graph of edge set array
private $vexs; // Vertex set
private $arc; // Edge set
private $arcData; // The side information of the graph to be built
private $krus; //kruscal Forest information is stored in the algorithm
public function Edge($vexsData, $arcData) {
$this->vexs = $vexsData;
$this->arcData = $arcData;
$this->createArc();
}
// Create Edge
private function createArc() {
foreach ($this->arcData as $key => $value) {
$key = str_split($key);
$this->arc[] = new EdgeArc($key[0], $key[1], $value);
}
}
// Sorting of opposite edge arrays by weight
public function sortArc() {
$this->quicklySort(0, count($this->arc) - 1, $this->arc);
return $this->arc;
}
// Adopt fast row
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 Algorithm
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";
}
}
}
// Find the tail node of a subtree
private function findRoot($node) {
while ($this->krus[$node] != "0") {
$node = $this->krus[$node];
}
return $node;
}
}
?>
Interested readers can debug and run 1 example of Kruskal algorithm in this paper, and I believe there will be new gains.