mgrechanik/kruskal

The implementation of the Kruskal algorithm to find a minimum spanning tree

1.0.0 2024-03-14 06:42 UTC

Requires

• php: ^8.0

Requires (Dev)

• phpunit/phpunit: 10
• yoast/phpunit-polyfills: ^2.0

BSD-3-Clause

• Mikhail Grechanik

• php
• graph
• minimum spanning tree
• kruskal
• Search algorithm
• path planning
• minimum weight spanning tree
• Minimum-cost subgraph
• mst
• Kruskal algorithm

README

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
        )

)

1. Distance of all tree

600

This code will find the next path: