Yog.FSharp
Getting Started Examples API Reference GitHub

Mst Module

Namespace: Yog
Assembly: Yog.FSharp.dll

Minimum Spanning Tree (MST) algorithms for finding optimal network connections.

A Minimum Spanning Tree connects all nodes in a weighted undirected graph with the minimum possible total edge weight. MSTs have applications in network design, clustering, and optimization problems.

Available Algorithms

Algorithm

Function

Best For

Kruskal's

kruskal/2

Sparse graphs, edge lists

Properties of MSTs

  • Connects all nodes with exactly V - 1 edges (for a graph with V nodes)
  • Contains no cycles
  • Minimizes the sum of edge weights
  • May not be unique if multiple edges have the same weight

Example Use Cases

  • Network Design: Minimizing cable length to connect buildings
  • Cluster Analysis: Hierarchical clustering via MST
  • Approximation: Traveling Salesman Problem approximations
  • Image Segmentation: Computer vision applications

References

Types

Type Description

Edge<'e>

Represents an edge in the minimum spanning tree.

Functions and values

Function or value Description

kruskal compare graph

Full Usage: kruskal compare graph

Parameters:
    compare : 'e -> 'e -> int
    graph : Graph<'n, 'e>

Returns: Edge<'e> list

Finds the Minimum Spanning Tree (MST) using Kruskal's algorithm.

Returns a list of edges that form the MST. The total weight of these edges is minimized while ensuring all nodes are connected.

Time Complexity: O(E log E) where E is the number of edges

Algorithm

  1. Sort all edges by weight in ascending order
  2. Iterate through sorted edges, adding each edge that doesn't form a cycle
  3. Use Union-Find to efficiently detect cycles

Example

1: 
2: 

let mstEdges = kruskal compare graph
// => [{ From = 1; To = 2; Weight = 5 }; { From = 2; To = 3; Weight = 3 }; ...]

Use Cases

  • Network design (minimum cost to connect all nodes)
  • Approximation algorithms for NP-hard problems
  • Cluster analysis (single-linkage clustering)

Comparison with Prim's Algorithm

  • Kruskal's: Processes edges globally, works well for sparse graphs
  • Prim's: Grows from a starting node, works well for dense graphs

Both produce optimal MSTs; choose based on graph density and implementation convenience.

val mstEdges: obj
val compare: e1: 'T -> e2: 'T -> int (requires comparison)

compare : 'e -> 'e -> int
graph : Graph<'n, 'e>
Returns: Edge<'e> list

prim compare graph

Full Usage: prim compare graph

Parameters:
    compare : 'e -> 'e -> int
    graph : Graph<'n, 'e>

Returns: Edge<'e> list

Finds the Minimum Spanning Tree (MST) using Prim's algorithm.

Returns a list of edges that form the MST. Unlike Kruskal's which processes all edges globally, Prim's grows the MST from a starting node by repeatedly adding the minimum-weight edge that connects a visited node to an unvisited node.

Time Complexity: O(E log V) where E is the number of edges and V is the number of vertices

Disconnected Graphs: For disconnected graphs, Prim's only returns edges for the connected component containing the starting node (the first node in the graph). Use Kruskal's if you need a minimum spanning forest that covers all components.

Algorithm

  1. Start from an arbitrary node (first node in the graph)
  2. Use a priority queue to track minimum-weight edges from visited to unvisited nodes
  3. Repeatedly extract the minimum edge, add it to the MST, and update the frontier

Example

1: 
2: 

let mstEdges = prim compare graph
// => [{ From = 1; To = 2; Weight = 5 }; { From = 2; To = 3; Weight = 3 }; ...]

Use Cases

  • Dense graphs where E ≈ V² (better cache locality than Kruskal's)
  • Incremental MST construction (can start from a specific node)
  • When you need the MST rooted at a specific node

Comparison with Kruskal's Algorithm

  • Prim's: Grows from a node, uses priority queue, O(E log V), single component only
  • Kruskal's: Processes edges by weight, uses Union-Find, O(E log E), handles all components

For dense connected graphs, Prim's is often faster. For sparse graphs or graphs with multiple components, Kruskal's is preferred.

val mstEdges: obj
val compare: e1: 'T -> e2: 'T -> int (requires comparison)

compare : 'e -> 'e -> int
graph : Graph<'n, 'e>
Returns: Edge<'e> list