disjoint set data structure - union-find - Algoritmit 2 demo 3
<?php
// mallia otettu täältä ja käännetty php:lle
// https://github.com/maxtilford/Miscellaneous/blob/master/Maze/UnionFind.java
class UnionFind {
public $forest;
// muodosta metsä, joka koostuu puista
// jokaisen puun vanhempi on aluksi puu itse
function __construct($universe) {
foreach ($universe as $parent) {
$this->forest[$parent] = new Tree($parent);
}
}
// Jos x ja y ovat eriävät, linkitetään ne toisiinsa
// ensin etsitään ja sitten linkitys
public function union($x, $y) {
$xRoot = $this->find($x);
$yRoot = $this->find($y);
if ($xRoot != $yRoot) {
$this->link($xRoot, $yRoot);
return true;
} else return false;
}
// yhdistää kaksi puuta toisiinsa, päivittää vanhemman tiedon (parent) ja tason, jolla solmu on (rank)
private function link($x, $y) {
$a = $this->forest[$x];
$b = $this->forest[$y];
if ($a->rank > $b->rank) {
$b->parent = $x;
} elseif ($a->rank < $b->rank) {
$a->parent = $y;
} else {
$a->parent = $y;
$b->rank++;
}
}
// Etsitään oikea solmu, ja tarvittaessa tiivistetään vaihtamalla vanhempi (parent)
public function find($x) {
if ($this->forest[$x]->parent != $x) {
$this->forest[$x]->parent = $this->find($this->forest[$x]->parent);
}
return $this->forest[$x]->parent;
}
}
// Puu, jolla on vanhempi (parent) ja taso (rank)
class Tree {
public $parent;
public $rank;
function __construct($p) {
$this->parent = $p;
$this->rank = 0;
}
}
$forest = new UnionFind(["kiuru", "lokki", "rastas", "sorsa", "varis"]);
$forest->union("sorsa", "rastas");
$forest->union("rastas", "varis");
$forest->union("varis", "kiuru");
$forest->union("kiuru", "lokki");
$forest->union("lokki", "sorsa"); // kaikkien vanhempi on tässä vaiheessa rastas
var_dump($forest);