Kruskal's algorithm: greedy on the cycle matroid

A disconnected graph has no spanning TREE, so connected is reported and the result is a spanning forest. Returning its weight as though it were a tree's would be quietly wrong.

Usage

morie_minimum_spanning_tree(edges, n_vertices, weights = NULL)

Arguments

edges

List of vertex pairs, vertices numbered from 1.

n_vertices

Number of vertices.

weights

Edge weights; default all 1.

Value

A list with weight, tree_edges, connected, n_components, warnings.

References

Kruskal JB (1956) Proc AMS 7(1):48-50.

Examples

K4E <- list(c(1, 2), c(2, 3), c(3, 4), c(4, 1), c(1, 3))
morie_minimum_spanning_tree(K4E, 4, c(4, 1, 3, 2, 5))
#> $weight
#> [1] 6
#> 
#> $tree_edges
#> [1] 2 4 3
#> 
#> $connected
#> [1] TRUE
#> 
#> $n_components
#> [1] 1
#> 
#> $n_edges_chosen
#> [1] 3
#> 
#> $expected_tree_edges
#> [1] 3
#> 
#> $n
#> [1] 4
#> 
#> $warnings
#> character(0)
#> 
#> $method
#> [1] "Kruskal's algorithm = greedy on the cycle matroid"
#>