Ir mājasdarbs (http://susurs.mii.lu.lv/juris/courses/Alg2015/Hw/progr_assign_2015.pdf), kuru pildu izmantojot PHP. Ievaddati tiek ņemti no txt faila
šāds ir kods:
function Kruskal(&$G) {
$len = count($G);
// 1. Make T the empty tree
$T = array();
// 2. Make a single node trees (sets) out of each vertex
$S = array();
foreach (array_keys($G) as $k) {
$S[$k] = array($k);
}
// 3. Sort the edges
$weights = array();
for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $i; $j++) {
if (!$G[$i][$j]) continue;
$weights[$i . ' ' . $j] = $G[$i][$j];
}
}
asort($weights);
$weights = array_reverse($weights);
var_dump($weights);
$summa = 0;
foreach ($weights as $k => $w) {
list($i, $j) = explode(' ', $k);
$iSet = find_set($S, $i);
$jSet = find_set($S, $j);
if ($iSet != $jSet) {
$summa += $w;
$T[] = "Edge: ($i, $j)";
union_sets($S, $iSet, $jSet);
}
}
var_dump($summa);
return $T;
}
function find_set(&$set, $index) {
foreach ($set as $k => $v) {
if (in_array($index, $v)) {
return $k;
}
}
return false;
}
function union_sets(&$set, $i, $j) {
$a = $set[$i];
$b = $set[$j];
unset($set[$i], $set[$j]);
$set[] = array_merge($a, $b);
}
$mst = Kruskal($matrix);
foreach ($mst as $v) {
echo $v . "<br>";
}
šāds sanāk masīvs ar grafu, kuru padod funkcijai Kruskal:
$G = array(
0 => array( 0,40,36,0,97,-77,0,81,0,36),
1 => array( 40,0,0,0,50,41,0,57,69,4),
2 => array( 36,0,0,26,36,82,55,0,87,0),
3 => array( 0,0,26,0,14,75,0,61,1,58),
4 => array( 97,50,36,14,0,2,55,66,15,76),
5 => array( -77,41,82,75,2,0,0,0,18,0),
6 => array( 0,0,55,0,55,0,0,0,0,0),
7 => array( 81,57,0,61,66,0,0,0,0,93),
8 => array( 0,69,87,1,15,18,0,0,0,99),
9 => array( 36,4,0,58,76,0,0,93,99,0),
);
Summai vajadzētu būt 615, bet man sanāk 738. Kur varētu būt problēma?
