Skip to contents

Solver for Minimum Spanning Tree

Source: R/minimumspanningtree.R
MinSpanningTree.Rd

The minimum spanning tree is the minimal connected acyclic subgraph of a graph, assuming the graph is undirected.

Usage

MinSpanningTree(
  arcSources,
  arcTargets,
  arcDistances,
  numNodes,
  algorithm = "Kruskal"
)

Arguments

arcSources

Vector corresponding to the source nodes of a graph's edges

arcTargets

Vector corresponding to the destination nodes of a graph's edges

arcDistances

Vector corresponding to the distances of nodes of a graph's edges

numNodes

The number of nodes in the graph

algorithm

Choices of algorithm include "Kruskal". "Kruskal" is the default.

Value

A named list containing three entries: 1) "sources": a vector corresponding the source nodes of the edges in the tree, 2) "targets": a vector corresponding the target nodes of the edges in the tree, and 3) "value": the total minimum spanning tree value.

Details

For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00610.html#ga233792b2c44a3581b85a775703e045af