README.md

Kruskal's algorithm to find a minimum spanning tree

Demo

Example of building a minimum spanning tree:

Installing

Installing through composer::

The preferred way to install this library is through composer.

Either run

composer require --prefer-dist mgrechanik/kruskal

or add

"mgrechanik/kruskal" : "~1.0.0"

to the require section of your composer.json.

How to use

Run the next code:

use mgrechanik\kruskal\Kruskal;

$matrix = [
    [ 0 , 263, 184, 335],
    [263,  0 , 287, 157],
    [184, 287,  0 , 259],
    [335, 157, 259,  0]
];
$kruskal = new Kruskal($matrix);
if ($kruskal->run()) {
    // 1)
    var_dump($kruskal->getMinimumSpanningTree());
    // 2)
    var_dump($kruskal->getDistance());
}

We will get:

1. Spanning tree as an array of edges

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 2
        )

    [1] => Array
        (
            [0] => 2
            [1] => 3
        )

    [2] => Array
        (
            [0] => 1
            [1] => 3
        )

)

2. Distance of all tree

600

This code will find the next path: